Flood Fill
- Flood Fill(洪水填充算法)是一类用来求连通块的算法,其实我感觉并没有很明确的定义,在不同的场景下可以用DFS,BFS或者并查集来解决这类问题
例题1.被围绕的区域
思路:
任何边界上的 'O' 都不会被填充为 'X'
任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'
题干中这两句话其实表达了只要求出从边界开始扩展的所有全'O'的连通块即可,其余的连通块全是'X'
我们可以从四条边上的'O'开始往里扩展,找到全'O'的连通块,并且打上标记
最后遍历整个区域,将打上标记的区域全部都染色为'O',没打上标记的区域全都染色为'X'
Java代码
class Solution {
char[][] board;
int n, m;
int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
public void solve(char[][] _board) {
board = _board;
if(board.length == 0 || board[0].length == 0) return;
n = board.length;
m = board[0].length;
for(int i = 0; i < n; i++){
if(board[i][0] == 'O') dfs(i,0);
if(board[i][m-1] == 'O') dfs(i,m-1);
}
for(int i = 0; i < m; i++){
if(board[0][i] == 'O') dfs(0,i);
if(board[n-1][i] == 'O') dfs(n-1,i);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == '#') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
_board = board;
}
void dfs(int x, int y){
board[x][y] = '#';
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O'){
dfs(a,b);
}
}
}
}
例题2.太平洋大西洋水流问题
思路
思路和前一题完全相同,顺流不太好做,我们考虑逆流的做法
分别从四条边向里搜索,找出能流动到太平洋的连通块和能流动到大西洋的连通块,交集就是答案
值得一提的是,怎样可以快速的求交集呢? 一般我们很容易想到开两个数组来遍历求交集
但这里我们使用位运算的方法来求交集,具体思路如下
只需要一个int数组,我们为每一个元素的二进制后两位赋予特殊含义:0为不能流动到,1为能流动到
例如:st[i][j] = 3 (3的2进制后两位为11,高位的1表示能流动到大西洋,低位的1表示能流动到太平洋)
所以我们只需要最后判断st数组中有哪些元素是3,就能求出交集部分了
Java代码
class Solution {
int[][] st;
int[][] matrix;
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
int n, m;
public List<List<Integer>> pacificAtlantic(int[][] _matrix) {
List<List<Integer>> res = new ArrayList<>();
matrix = _matrix;
if(matrix.length == 0 || matrix[0].length == 0) return res;
n = matrix.length;
m = matrix[0].length;
st = new int[n][m];
for(int i = 0; i < n; i++) dfs(i, 0, 1);
for(int i = 0; i < m; i++) dfs(0, i, 1);
for(int i = 0; i < n; i++) dfs(i, m-1, 2);
for(int i = 0; i < m; i++) dfs(n-1, i, 2);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(st[i][j] == 3){
List<Integer> list = new ArrayList<>();
list.add(i);
list.add(j);
res.add(new ArrayList<>(list));
}
}
}
return res;
}
void dfs(int x, int y, int t){
if((st[x][y] & t) != 0) return;
st[x][y] |= t;
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m && matrix[a][b] >= matrix[x][y]){
dfs(a, b, t);
}
}
}
}