DFS flood filling
这类在 2D 矩阵上 DFS 的题都挺送分的，写的时候重在简洁。 和这题非常相似的还有下面的 Number of Islands.
边界处理在 DFS 一开始做，免得后面的多向 DFS 里再重写
如果要 backtrack，就先把自己格子设成其他字符再 DFS，免得死循环
public class Solution {
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int row, int col) {
if(index == word.length()) return true;
if(row < 0 || row >= board.length) return false;
if(col < 0 || col >= board[0].length) return false;
if(board[row][col] != word.charAt(index)) return false;
board[row][col] = '#';
boolean rst = (
dfs(board, word, index + 1, row - 1, col) ||
dfs(board, word, index + 1, row + 1, col) ||
dfs(board, word, index + 1, row, col + 1) ||
dfs(board, word, index + 1, row, col - 1)
);
board[row][col] = word.charAt(index);
return rst;
}
}和上一道 Word Search 就完全是一个套路，只是细节不同，这题 DFS 的主要动作是 flood-filling，把相连接的所有格子都填上，算作一个岛。既然不是 search 就不需要 backtracking 那一套了，填就行。
public class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == '1'){
dfs(grid, i , j);
count ++;
}
}
}
return count;
}
private void dfs(char[][] grid, int x, int y){
if(x < 0 || x >= grid.length) return;
if(y < 0 || y >= grid[0].length) return;
if(grid[x][y] == '0') return;
grid[x][y] = '0';
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
}
}第一次写的时候用了个 HashSet 记录哪些点访问过，显得麻烦，还浪费了额外空间。
这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。
这段代码的逻辑就是从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖；最后过一遍的时候除了 'S' 的都标成 'X' 就好了。
然而在大矩阵上 stackoverflow... 看来无脑 dfs 的做法还不够经济啊。。。
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
dfs(board, 0, i);
}
if(board[rows - 1][i] == 'O'){
dfs(board, rows - 1, i);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
dfs(board, i, 0);
}
if(board[i][cols - 1] == 'O'){
dfs(board, i, cols - 1);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int row, int col){
if(row < 0 || row >= board.length) return;
if(col < 0 || col >= board[0].length) return;
if(board[row][col] != 'O') return;
board[row][col] = 'S';
dfs(board, row + 1, col);
dfs(board, row - 1, col);
dfs(board, row, col + 1);
dfs(board, row, col - 1);
}
}写了个 BFS 的在一个中型矩阵上 TLE了，我有点方。。
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
queue.offer(i);
bfs(board, 0, i, queue);
}
if(board[rows - 1][i] == 'O'){
queue.offer((rows - 1) * cols + i);
bfs(board, rows - 1, i, queue);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
queue.offer(i * cols);
bfs(board, i, 0, queue);
}
if(board[i][cols - 1] == 'O'){
queue.offer(i * cols + cols - 1);
bfs(board, i, cols - 1, queue);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void bfs(char[][] board, int row, int col, Queue<Integer> queue){
int rows = board.length;
int cols = board[0].length;
if(!isValid(row, rows, col, cols)) return;
while(!queue.isEmpty()){
Integer index = queue.poll();
int x = index / cols;
int y = index % cols;
if(board[x][y] == 'O') board[x][y] = 'S';
if(isValid(x + 1, rows, y, cols) && board[x + 1][y] == 'O') queue.offer((x + 1) * cols + y);
if(isValid(x - 1, rows, y, cols) && board[x - 1][y] == 'O') queue.offer((x - 1) * cols + y);
if(isValid(x, rows, y + 1, cols) && board[x][y + 1] == 'O') queue.offer(x * cols + y + 1);
if(isValid(x, rows, y - 1, cols) && board[x][y - 1] == 'O') queue.offer(x * cols + y - 1);
}
return;
}
private boolean isValid(int row, int rows, int col, int cols){
if(row < 0 || row >= rows) return false;
if(col < 0 || col >= cols) return false;
return true;
}
}同样的 DFS 逻辑，做了如下改动之后就不会 stackoverflow 了：
DFS 时不进入最外围一圈的位置
简单来讲是在尽可能限制 DFS call stack 的层数，控制 DFS 的深度。从正确性上讲，上面的写法也是正确的，但是在极端情况下如果某一个从边沿出发的 DFS 连通了另一个边沿出发的 DFS，会导致一次的搜索路径非常长，于是 stackoverflow. 既然边沿的格子无论如何都要检查一遍，就把外圈封住，减少每个起点的 search tree depth.
public class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
for(int i = 0; i < cols; i++){
if(board[0][i] == 'O'){
dfs(board, 0, i);
}
if(board[rows - 1][i] == 'O'){
dfs(board, rows - 1, i);
}
}
for(int i = 1; i < rows - 1; i++){
if(board[i][0] == 'O'){
dfs(board, i, 0);
}
if(board[i][cols - 1] == 'O'){
dfs(board, i, cols - 1);
}
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'S'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int row, int col){
if(row < 0 || row >= board.length) return;
if(col < 0 || col >= board[0].length) return;
if(board[row][col] != 'O') return;
board[row][col] = 'S';
// DFS 时不进入最外圈
if(row + 2 < board.length && board[row + 1][col] == 'O') dfs(board, row + 1, col);
if(row - 2 >= 0 && board[row - 1][col] == 'O') dfs(board, row - 1, col);
if(col + 2 < board[0].length && board[row][col + 1] == 'O') dfs(board, row, col + 1);
if(col - 2 >= 0 && board[row][col - 1] == 'O') dfs(board, row, col - 1);
}
}这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.
不过只是在这个问题上，不是很简洁。
Last updated