Flood Fill

时间是：11-6

在2d array上下左右搜索，同时把搜索过的地方标记。 这种做法省空间，一般用在集合合并的题里面。

Word Search

这题有点像是图上的dfs搜索问题，所以需要一个数组来记录是否访问过该节点。记得退出递归的时候要把它恢复。

public class Solution {
    public boolean exist(char[][] board, String word) {
        // go over the 2d array, different start point 
        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 idx, int i, int j) {
        if(idx >= word.length()) return true;
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        // prune
        if(board[i][j] != word.charAt(idx)) return false;
        // 为了不重复访问同一个位置
        board[i][j] = '0';
        boolean result = dfs(board, word, idx + 1, i - 1, j) ||
                         dfs(board, word, idx + 1, i + 1, j) ||
                         dfs(board, word, idx + 1, i, j - 1) ||
                         dfs(board, word, idx + 1, i, j + 1);
        board[i][j] = word.charAt(idx);

        return result;
    }
}

Number of Islands

把相连接的所有格子都填上，算作一个岛。既然不是 search 就不需要 backtracking 那一套。

public int numIslands(char[][] grid) {
    int count = 0;
    for(int i = 0; i < grid.length; i++) {
        for(int j = 0; j < gird[0].length; j++) {
            if(grid[i][j] == 1) {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
    if(grid[i][j] != '1') return;

    grid[i][j] = '0';

    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

Surrounded Regions

这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。

从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖； 最后过一遍的时候除了 'S' 的都标成 'X' 就好了。

因为四个边上的O 是不能改变的，以及和边上的O相连的O也是不能变成X的。

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) {
            return;
        }
        int n = board.length;
        int m = board[0].length;
        // 上下边
        for(int i = 0; i < m; i++) {
            if(board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if(board[n - 1][i] == 'O') {
                dfs(board, n - 1, i);
            }
        }
        // 左右边
        for(int i = 0; i < n; i++) {
            if(board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if(board[i][m - 1] == 'O') {
                dfs(board, i, m - 1);
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'V') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        if(board[i][j] != 'O') return;

        board[i][j] = 'V';

        dfs(board, i - 1,j);
        dfs(board, i,j - 1);
        dfs(board, i + 1,j);
        dfs(board, i,j + 1);
    }
}

这个解法在大数据集上会StackOverflow，说明进入的层数太深了。 我们可以在DFS的时候不让它进入最外面的一层。

在极端情况下如果某一个从边沿出发的 DFS 连通了另一个边沿出发的 DFS，会导致一次的搜索路径非常长，于是 stackoverflow。

我们把周围的一圈封死，减少每条路劲的最大长度

if(i + 2 < board.length && board[i + 1][j] == 'O')    dfs(board, i + 1, j);
if(i - 2 >= 0 && board[i - 1][j] == 'O')              dfs(board, i - 1, j);
if(j + 2 < board[0].length && board[i][j + 1] == 'O') dfs(board, i, j + 1);
if(j - 2 >= 0 && board[i][j - 1] == 'O')              dfs(board, i, j - 1);