MENU

LeetCode130. 被围绕的区域

July 15, 2018 • Read: 238 • LeetCode

image

 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);
    }
}
最后编辑于: August 12, 2018
Archives Tip
QR Code for this page
Tipping QR Code