美文网首页
LeetCode 130. 被围绕的区域(dfs,bfs,并查集

LeetCode 130. 被围绕的区域(dfs,bfs,并查集

作者: lhsjohn | 来源:发表于2019-04-02 01:03 被阅读0次
    给定一个二维的矩阵,包含 '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
    解释:
    
    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
    
    

    这道题有三种解法,可以用dfs或者bfs或者并查集来做
    使用bfs或者dfs思路:
    开一个二维布尔数组,记录哪些区域被遍历过。
    枚举所有边界上的'O',从该位置做bfs或者dfs,只遍历是'O'的位置,并将所有遍历到的位置都标记成true。
    将所有未遍历到的位置变成'X'。

    1.dfs

    
        boolean [][]visited;
        int row,col;
    
        public void solve(char[][] board) {
    
           row = board.length;
    
           if (row==0){
               return;
           }
           col = board[0].length;
    
            visited = new boolean[row][col];
    
    
            for (int i =0;i<row;i++){
                if (board[i][0]=='O')  dfs(i,0,board);
                if (board[i][col-1]=='O') dfs(i,col-1,board);
            }
    
            for (int i=0;i<col;i++){
                if (board[0][i]=='O') dfs(0,i,board);
                if (board[row-1][i]=='O') dfs(row-1,i,board);
            }
    
    
            for (int i=0;i<row;i++){
                for (int j=0;j<col;j++){
                    if (!visited[i][j]){
                        board[i][j] = 'X';
                    }
                }
            }
    
    
        }
    
    
        public void dfs(int x,int y,char[][]board){
    
               visited[x][y] = true;
    
               int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1};
    
               for (int i=0;i<4;i++){
                   int a = x + dx[i];
                   int b = y + dy[i];
                  if (a>=0&&a<row&&b>=0&&b<col&&!visited[a][b]&&board[a][b]=='O'){
                      dfs(a,b,board);
                  }
    
    
               }
    
    
        }
    
    

    2.bfs

      //bfs 做法
    
        boolean [][]visited;
        int row,col;
        public void solve2(char[][]board){
            int row = board.length;
            if (row==0) return;
            int col = board[0].length;
    
            visited = new boolean[row][col];
            Queue<Pair<Integer,Integer>> queue = new LinkedList<>();
            for (int i=0;i<row;i++){
                if (board[i][0]=='O'){
                    visited[i][0] = true;
                    Pair<Integer,Integer> pair = new Pair<>(i,0);
                    queue.add(pair);
                }
    
                if (board[i][col-1]=='O'){
                    visited[i][col-1] = true;
                    Pair<Integer,Integer> pair = new Pair<>(i,col-1);
                    queue.add(pair);
                }
    
            }
    
    
            for (int i=0;i<col;i++){
                if (board[0][i]=='O'){
                    visited[0][i] = true;
                    Pair<Integer,Integer> pair = new Pair<>(0,i);
                    queue.add(pair);
                }
                if (board[row-1][i]=='O'){
                    visited[row-1][i] = true;
                    Pair<Integer,Integer> pair = new Pair<>(row-1,i);
                    queue.add(pair);
                }
            }
    
    
            int dx[] = {-1,0,1,0}, dy[]={0,1,0,-1};
    
            while (!queue.isEmpty()){
                Pair <Integer,Integer> pair = queue.poll();
                int x = pair.getKey();
                int y = pair.getValue();
                visited[x][y] = true;
    
                for (int i=0;i<4;i++){
                    int a = x + dx[i];
                    int b = y + dy[i];
    
                    if (a>=0&&a<row&&b>=0&&b<col&&!visited[a][b]&&board[a][b]=='O'){
                        queue.add(new Pair(a,b));
                    }
    
                }
    
            }
    
            for (int i=0;i<row;i++){
                for (int j = 0;j<col;j++){
                    if (!visited[i][j]){
                        board[i][j] = 'X';
                    }
                }
            }
    
    
        }
    
    

    3.并查集做法 思路:把所有不被'X'包围的'O'放在同一个集合里,然后遍历数组,将不在集合中的'O'转换为'X'。

    
        //并查集做法
        int[] parent ;
        int rows,cols;
        final  int manx = 100005;
    
        int find(int x){
            while (x!=parent[x]){
                x = parent[x];
            }
            return x;
        }
    
        void Union(int x,int y){
            x = find(x);
            y = find(y);
    
            if (x > y){
                parent[x] = y;
            }else if (x < y){
                parent[y] = x;
            }
    
        }
    
        boolean same(int x,int y){
            return find(x)==find(y);
        }
    
    
    
        public void solve3(char[][]board){
             rows = board.length;
            if (rows==0) return;
             cols = board[0].length;
    
            parent = new int[manx];
    
            for (int i=0;i<manx;i++){
                parent[i] = i;
            }
    
            int dx[] = {-1,0,1,0}, dy[]={0,1,0,-1};
    
            for (int i=0;i<rows;i++){
                for (int j=0;j<cols;j++){
                    if ((i==0 || i==rows-1 || j==0 || j==cols-1) && board[i][j]=='O'){
                        Union(i*rows+j,rows*cols);
                    }else if (board[i][j]=='O'){
                        for (int k =0;k<4;k++){
                            int x = i + dx[k];
                            int y = j + dy[k];
                            if (board[x][y]=='O'){
                                Union(i*rows+j,x*rows+y);
                            }
                        }
    
    
                    }
                }
            }
    
            for (int i=0;i<rows;i++){
                for (int j =0;j<cols;j++){
                    if (!same(i*rows+j,rows*cols)) board[i][j] = 'X';
                }
            }
    
    
    
        }
    
    
    

    相关文章

      网友评论

          本文标题:LeetCode 130. 被围绕的区域(dfs,bfs,并查集

          本文链接:https://www.haomeiwen.com/subject/eivibqtx.html