被围绕的区域

题目：
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

思想：
利用上下左右的递归，蔓延做标记，求得结果。

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m==0) {
            return;
        }
        int n = board[0].length;
        if(m==1 && n==1 && board[0][0]=='O') {
            return;
        }
        // 上
        for(int i=0;i<n-1;i++) {
            if(board[0][i]=='O') {
                fSolve(board,0,i);
            }
        }
        // 右
        for(int i=0;i<m-1;i++) {
            if(board[i][n-1]=='O') {
                fSolve(board,i,n-1);
            }
        }
        // 下
        for(int i=n-1;i>0;i--) {
            if(board[m-1][i]=='O') {
                fSolve(board,m-1,i);
            }
        }
        // 左
        for(int i=m-1;i>0;i--) {
            if(board[i][0]=='O') {
                fSolve(board,i,0);
            }
        }
        // 处理标记O的情况
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]=='O') {
                    board[i][j] = 'X';
                }
            }
        }
        // 处理标记#的情况
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]=='#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void fSolve(char[][] board, int indexI, int indexJ) {
        if(indexI<0 || indexI>board.length-1 || indexJ<0 || indexJ>board[0].length-1) {
            return;
        }
        if(board[indexI][indexJ]=='O') {
            board[indexI][indexJ]='#';
            fSolve(board,indexI-1,indexJ);
            fSolve(board,indexI+1,indexJ);
            fSolve(board,indexI,indexJ+1);
            fSolve(board,indexI,indexJ-1);
        }
    }
    
    
}

优化代码

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m==0) {
            return;
        }
        int n = board[0].length;
        if(m==1 && n==1 && board[0][0]=='O') {
            return;
        }
        // 处理边界蔓延
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                boolean isBorder = (i==0 || i==m-1 || j==0 || j==n-1);
                if(isBorder&&board[i][j]=='O') {
                    fSolve(board,i,j);
                }
            }
        }
        // 处理最终的结果
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]=='O') {
                    board[i][j] = 'X';
                }
                if(board[i][j]=='#') {
                    board[i][j] = 'O';
                }
            }
        }

    }
    
    private void fSolve(char[][] board, int indexI, int indexJ) {
        if(indexI<0 || indexI>board.length-1 || indexJ<0 || indexJ>board[0].length-1) {
            return;
        }
        if(board[indexI][indexJ]=='O') {
            board[indexI][indexJ]='#';
            fSolve(board,indexI-1,indexJ);
            fSolve(board,indexI+1,indexJ);
            fSolve(board,indexI,indexJ+1);
            fSolve(board,indexI,indexJ-1);
        }
    }
    
    
}