题目

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

热门阅读

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