Matrix Search 矩阵搜索类

79. Word Search

题目挺简单的，重在代码的简洁性。

class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0
           || word == null || word.length() == 0)
            return false;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, word, 1, visited))
                    return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int i, int j, String word, int index, boolean[][] visited){
        if (index == word.length())
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs){
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || board[x][y] != word.charAt(index))
                continue;
            if (dfs(board, x, y, word, index+1, visited))
                return true;
        }
        visited[i][j] = false;
        return false;
    }
}

200. Number of Islands

和上一题一个套路，只不过这道题里因为每个cell最多只访问一次，所以每经过一个'1'的cell，直接改成'0'就行了（这个操作有个专门的名字，叫"flood-filling"）。

class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    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'){
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    public void dfs (char[][] grid, int i, int j){
        if (grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        for (int[] dir : dirs){
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length)
                continue;
            dfs(grid, x, y);
        }
    }
}

[130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/discuss/)

这道题的思路是，从四边上遇到的O往里DFS，把遇到的O全改成S。最后再遍历一遍矩阵，遇到的S改成O，遇到的O改成X。

一个优化的trick是：DFS时不进入最外圈。不做这个优化的话会stack overflow。

```java
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++){
            if (board[i][0] == 'O')
                dfs(board, i, 0, m, n);
            if (board[i][n-1] == 'O' && n > 1)
                dfs(board, i, n-1, m, n);
        }
        for (int j = 0; j < n; j++){
            if (board[0][j] == 'O')
                dfs(board, 0, j, m, n);
            if (board[m-1][j] == 'O' && m > 1)
                dfs(board, m-1, j, m, n);
        }
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'S')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }

    public void dfs(char[][] board, int i, int j, int m, int n){
        board[i][j] = 'S';
        if (i > 1 && board[i-1][j] == 'O')  // up
            dfs(board, i-1, j, m, n);
        if (i < m-2 && board[i+1][j] == 'O') // down
            dfs(board, i+1, j, m, n);
        if (j > 1 && board[i][j-1] == 'O') // left
            dfs(board, i, j-1, m, n);
        if (j < n-2 && board[i][j+1] == 'O') // right
            dfs(board, i, j+1, m, n);
    }
}

这道题也可以用union-find来做：

1. 对每一个遍历时遇到的O cell，都把它和相邻的O cell进行union。
2. 如果这个O cell是在边界上，就把它和一个dummy node（可以想象成位于外面海洋中的一个node）进行union。
3. 再遍历一遍所有cell。如果是O cell，而且没有和dummy node在一个连通分量里，说明它被包围了，要flip成X。

只不过比较慢。代码在union-find那章有， 就不复制粘贴了。