链接：130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

重要的就是这句话，替换的区域一定不与边界相连，所以可以吧与边界相连的区域标记出来，最后没有被标记的O一定就是被X围绕的。

具体过程：

1. 遍历四个边界上的点，分别从每个点出发使用DFS标记(#)与边界点相连的区域
2. 边界遍历完成后，剩下的所有O一定是不与边界相连且被X围绕的
3. 将违背标记的O置为X，将被标记的#还原为O

class Solution {
 
    // 上下左右四个方向遍历
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    // 记录行，列数
    int m, n;

    public void solve(char[][] board) {

        if (board == null || board[0].length == 0) {
            return;
        }

        m = board.length;
        n = board[0].length;

        // 从四个边界的点出发，将所有与边界相连的点标记
        for (int i = 0; i <= m-1; i++) {
            dfs(board, i, 0);
            dfs(board, i, n-1);
        }
        for (int i = 0; i <= n-1; i++) {
            dfs(board, 0, i);
            dfs(board, m-1, i);
        }
        // 上面两个for循环执行后所有与边界相邻的点都会被标记为特殊字符


        // 全部遍历一次
        // 将所有被标记为#的点重新恢复成O, 仍旧是O的点则一定是被X包围且不与边界相连的，可以置为X
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    /**
     * @param board
     * @param x
     * @param y
     * @return
     */
    private void dfs(char[][] board, int x, int y) {
        // 如果没有越界并且当前字符是'O'则继续递归遍历
        if (inArea(x, y) && board[x][y]=='O') {
            board[x][y] = '#';
            for (int i = 0; i < direction.length; i++) {
                int newX = x + direction[i][0];
                int newY = y + direction[i][1];
                dfs(board, newX, newY);
            }
        }
    }

    /**
     * 判断当前坐标点是否越界
     *
     * @param x
     * @param y
     * @return
     */
    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

}