【Leetcode】130.被包围的区域

拼搏现实的明天。 2022-01-20 11:57 200阅读 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遍历的题目了。题目中解释说被包围的区间不会存在于边界上，所以我们会想到边界上的o要特殊处理，只要把边界上的o特殊处理了，那么剩下的o替换成x就可以了。问题转化为，如何**寻找和边界联通的o**，我们需要考虑如下情况。

X X X X
    X O O X
    X X O X
    X O O X
    复制代码

这时候的o是不做替换的。因为和边界是连通的。为了记录这种状态，我们把这种情况下的o换成\#作为占位符，待搜索结束之后，遇到o替换为x（**和边界不连通的o**）；遇到\#，替换回o(**和边界连通的o**)。

**如何寻找和边界联通的o?** 从边界出发，对图进行dfs和bfs即可。这里简单总结下dfs和dfs。

*  bfs递归。可以想想二叉树中如何递归的进行层序遍历。
 *  bfs非递归。一般用队列存储。
 *  dfs递归。最常用，如二叉树的先序遍历。
 *  dfs非递归。一般用stack。

那么基于上面这种想法，我们有四种方式实现。

## dfs递归 ##

class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘o开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int i, int j) {
            if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
                // board[i][j] == '#' 说明已经搜索过了. 
                return;
            }
            board[i][j] = '#';
            dfs(board, i - 1, j); // 上
            dfs(board, i + 1, j); // 下
            dfs(board, i, j - 1); // 左
            dfs(board, i, j + 1); // 右
        }
    }
    复制代码

## dfs 非递归 ##

非递归的方式，我们需要记录每一次遍历过的位置，我们用stack来记录，因为它先进后出的特点。而位置我们定义一个内部类Pos来标记横坐标和纵坐标。注意的是，在写非递归的时候，我们每次查看stack顶，但是并不出stack，直到这个位置上下左右都搜索不到的时候出Stack。

class Solution {
        public class Pos{
            int i;
            int j;
            Pos(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘第一个是o的开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int i, int j) {
            Stack<Pos> stack = new Stack<>();
            stack.push(new Pos(i, j));
            board[i][j] = '#';
            while (!stack.isEmpty()) {
                // 取出当前stack 顶, 不弹出.
                Pos current = stack.peek();
                // 上
                if (current.i - 1 >= 0 
                    && board[current.i - 1][current.j] == 'O') {
                    stack.push(new Pos(current.i - 1, current.j));
                    board[current.i - 1][current.j] = '#';
                  continue;
                }
                // 下
                if (current.i + 1 <= board.length - 1 
                    && board[current.i + 1][current.j] == 'O') {
                    stack.push(new Pos(current.i + 1, current.j));
                    board[current.i + 1][current.j] = '#';      
                    continue;
                }
                // 左
                if (current.j - 1 >= 0 
                    && board[current.i][current.j - 1] == 'O') {
                    stack.push(new Pos(current.i, current.j - 1));
                    board[current.i][current.j - 1] = '#';
                    continue;
                }
                // 右
                if (current.j + 1 <= board[0].length - 1 
                    && board[current.i][current.j + 1] == 'O') {
                    stack.push(new Pos(current.i, current.j + 1));
                    board[current.i][current.j + 1] = '#';
                    continue;
                }
                // 如果上下左右都搜索不到,本次搜索结束，弹出stack
                stack.pop();
            }
        }
    }
    
    复制代码

## bfs 非递归 ##

dfs非递归的时候我们用stack来记录状态，而bfs非递归，我们则用队列来记录状态。和dfs不同的是，dfs中搜索上下左右，只要搜索到一个满足条件，我们就顺着该方向继续搜索，所以你可以看到dfs代码中，只要满足条件，就入Stack，然后continue本次搜索，进行下一次搜索，直到搜索到没有满足条件的时候出stack。而bfs中，我们要把上下左右满足条件的都入队，所以搜索的时候就不能continue。大家可以对比下两者的代码，体会bfs和dfs的差异。

class Solution {
        public class Pos{
            int i;
            int j;
            Pos(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘第一个是o的开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        bfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        public void bfs(char[][] board, int i, int j) {
            Queue<Pos> queue = new LinkedList<>();
            queue.add(new Pos(i, j));
            board[i][j] = '#';
            while (!queue.isEmpty()) {
                Pos current = queue.poll();
                // 上
                if (current.i - 1 >= 0 
                    && board[current.i - 1][current.j] == 'O') {
                    queue.add(new Pos(current.i - 1, current.j));
                    board[current.i - 1][current.j] = '#';
                  	// 没有continue.
                }
                // 下
                if (current.i + 1 <= board.length - 1 
                    && board[current.i + 1][current.j] == 'O') {
                    queue.add(new Pos(current.i + 1, current.j));
                    board[current.i + 1][current.j] = '#';      
                }
                // 左
                if (current.j - 1 >= 0 
                    && board[current.i][current.j - 1] == 'O') {
                    queue.add(new Pos(current.i, current.j - 1));
                    board[current.i][current.j - 1] = '#';
                }
                // 右
                if (current.j + 1 <= board[0].length - 1 
                    && board[current.i][current.j + 1] == 'O') {
                    queue.add(new Pos(current.i, current.j + 1));
                    board[current.i][current.j + 1] = '#';
                }
            }
        }
    }
    复制代码

# bfs 递归 #

bfs 一般我们不会去涉及，而且比较绕，之前我们唯一A过的用bfs递归的方式是层序遍历二叉树的时候可以用递归的方式。

## 并查集 ##

并查集这种数据结构好像大家不太常用，实际上很有用，我在实际的production code中用过并查集。并查集常用来解决连通性的问题，即将一个图中连通的部分划分出来。当我们判断图中两个点之间是否存在路径时，就可以根据判断他们是否在一个连通区域。 而这道题我们其实求解的就是和边界的O在一个连通区域的的问题。

并查集的思想就是，同一个连通区域内的所有点的根节点是同一个。将每个点映射成一个数字。先假设每个点的根节点就是他们自己，然后我们以此输入连通的点对，然后将其中一个点的根节点赋成另一个节点的根节点，这样这两个点所在连通区域又相互连通了。 并查集的主要操作有：

*  find(int m)：这是并查集的基本操作，查找m的根节点。
 *  isConnected(int m,int n)：判断m，n两个点是否在一个连通区域。
 *  union(int m,int n):合并m，n两个点所在的连通区域。

class UnionFind {
        int[] parents;
    
        public UnionFind(int totalNodes) {
            parents = new int[totalNodes];
            for (int i = 0; i < totalNodes; i++) {
                parents[i] = i;
            }
        }
    		// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
        void union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            if (root1 != root2) {
                parents[root2] = root1;
            }
        }
    
        int find(int node) {
            while (parents[node] != node) {
                // 当前节点的父节点 指向父节点的父节点.
                // 保证一个连通区域最终的parents只有一个.
                parents[node] = parents[parents[node]];
                node = parents[node];
            }
    
            return node;
        }
    
        boolean isConnected(int node1, int node2) {
            return find(node1) == find(node2);
        }
    }
    复制代码

我们的思路是把所有边界上的O看做一个连通区域。遇到O就执行并查集合并操作，这样所有的O就会被分成两类

*  和边界上的O在一个连通区域内的。这些O我们保留。
 *  不和边界上的O在一个连通区域内的。这些O就是被包围的，替换。

由于并查集我们一般用一维数组来记录，方便查找parants，所以我们将二维坐标用node函数转化为一维坐标。

public void solve(char[][] board) {
            if (board == null || board.length == 0)
                return;
    
            int rows = board.length;
            int cols = board[0].length;
    
            // 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点
            UnionFind uf = new UnionFind(rows * cols + 1);
            int dummyNode = rows * cols;
    
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (board[i][j] == 'O') {
                        // 遇到O进行并查集操作合并
                        if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                            // 边界上的O,把它和dummyNode 合并成一个连通区域.
                            uf.union(node(i, j), dummyNode);
                        } else {
                            // 和上下左右合并成一个连通区域.
                            if (i > 0 && board[i - 1][j] == 'O')
                                uf.union(node(i, j), node(i - 1, j));
                            if (i < rows - 1 && board[i + 1][j] == 'O')
                                uf.union(node(i, j), node(i + 1, j));
                            if (j > 0 && board[i][j - 1] == 'O')
                                uf.union(node(i, j), node(i, j - 1));
                            if (j < cols - 1 && board[i][j + 1] == 'O')
                                uf.union(node(i, j), node(i, j + 1));
                        }
                    }
                }
            }
    
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (uf.isConnected(node(i, j), dummyNode)) {
                        // 和dummyNode 在一个连通区域的,那么就是O；
                        board[i][j] = 'O';
                    } else {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    
        int node(int i, int j) {
            return i * cols + j;
        }
    }
    复制代码

# 热门阅读 #

*  [看了很多技术书，为啥仍然写不出项目？][Link 1]
 *  [【Spring】IOC是啥有什么好处][Spring_IOC]
 *  [百度社招面试题——Redis实现分布式锁][Redis]
 *  [【Leetcode】114. 二叉树展开为链表][Leetcode_114.]

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2F9r1nZihRrW2FVZVvKg8P3A
[Spring_IOC]: https://link.juejin.im?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2FVB5MSionhHEGFbdlRIjWDg
[Redis]: https://link.juejin.im?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2F6_uJ03bMyY8HeUDeb4HxYQ
[Leetcode_114.]: https://link.juejin.im?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2F4IxEj0B_CUW6B46HrZQmdA