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

给定一个二维的矩阵，包含 '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';
            }
        }



    }