首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode130. 被围绕的区域

LeetCode130. 被围绕的区域

作者头像
mathor
发布2018-07-24 15:30:47
3690
发布2018-07-24 15:30:47
举报
文章被收录于专栏:mathormathor
image
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);
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-07-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档