LeetCode130. 被围绕的区域

bfs 题，主函数中枚举每一个起点，如果是 'O' 就开始 bfs 搜索，首先将 'O' 变为 'X'，然后将周围是 'O' 都入队。这里有个地方要注意，如果 'O' 并不是被四个 'X' 包围，也就是说 'O' 贴边，这种情况我们就不应该将他变为 'X'，所以程序中我用一个 boolean 变量 isHuan 来记录是否应该在枚举完之后将其变回去，而为了不让每一个点都 “挖了” 再 “填回去”，每次访问到的点，我都用一个二维数组标记为访问过，只有没访问过的点才访问

class Solution {
    public int n,m;
    public int[] qx = new int[100000];
    public int[] qy = new int[100000];
    public int[][] dr = {{1,0},{-1,0},{0,1},{0,-1}};
    public boolean[][] v = new boolean[1000][1000];
    public boolean isHuan;
    public int check(int x,int y,int tail,char[][] board) {
        if(x >= 0 && x < n && y >= 0 && y < m) {
            if(board[x][y] == 'O') {
                qx[tail] = x;
                qy[tail] = y;
                board[x][y] = 'X';
                v[x][y] = true; 
                ++tail;
            } 
        } else {
            isHuan = true;
        }
        return tail;
    }       
    public void bfs(int x,int y,char[][] board) {
        isHuan = false;
        int head = 0;
        int tail = 1;//[hear,tail)
        qx[0] = x;
        qy[0] = y;
        board[x][y] = 'X';
        v[x][y] = true;
        while(head < tail) {
            int i;
            for(i = 0;i < 4;i++) {
                int nx = qx[head] + dr[i][0];
                int ny = qy[head] + dr[i][1];
                tail = check(nx,ny,tail,board);
            }
            if(i == 4)
                ++head;
        }
        if(isHuan)
            for(int i = 0;i < tail;i++) 
                board[qx[i]][qy[i]]= 'O';           
    }
    public void solve(char[][] board) {
        if(board.length == 0 || board[0].length == 0) 
            return;
        n = board.length;
        m = board[0].length;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                v[i][j] = false;
        for(int i = 0;i < n;i++) 
            for(int j = 0;j < m;j++) 
                if(board[i][j] == 'O' && !v[i][j])
                    bfs(i,j,board);
    }
}