LeetCode 130. 被围绕的区域
目录
题目描述
题意分析
给一个只含
X和O的矩阵，要求把所有被X完全包围的O就地改成X。注意是原地修改，函数没有返回值，所以必须在同一个二维数组上完成。「被围绕」这个词需要精确化。一个
O属于某个上下左右四连通的O连通块，只要这个连通块里有任何一格贴着矩阵的四条边，整块就都能「逃出去」，不算被围绕；反过来，只有整块完全嵌在内部、四周被X封死，才算被围绕。判定的单位是连通块而不是单个格子，这一点必须先想清楚。于是就得到了本题真正的判据，而且它是反向的：与边界连通的
O一定不被围绕，其余的O一定被围绕。 与其去证明某个O出不去（要看遍整块并确认没有一格触边），不如去证明哪些O出得去（从边界出发一路走过去就行）——后者是可达性问题，一次搜索就能全部标出来。边界情况：矩阵为空或只有一行一列时，所有格子本身就在边界上，任何
O都不会被翻转；矩阵全是X或全是O时同样不发生任何改动。
解法：边界 BFS 标记安全区域
核心思路
正面判断一个
O连通块是否被包围，需要搜索完整块后再确认它有没有接触边界。反过来更简单：所有与边界O四连通的格子都不会被包围，其余O一定会被包围。因此先把四条边上的
O加入队列，再用 BFS 把所有可达的O临时标记为#。搜索结束后：
- 仍为
O的格子无法到达边界，应翻转成X。- 标记为
#的格子与边界连通，应恢复成O。直接借用矩阵中的临时字符充当访问标记，不需要额外的
visited数组。正确性：BFS 从边界出发且只沿
O移动，所以被标记的格子恰好是「与边界连通的O」集合，它们都不能被捕获。若某个未标记的O也不被包围，它就应存在一条通往边界的O路径，从而会被 BFS 标记，产生矛盾。因此剩余O恰好都是应被翻转的区域。
解题步骤
- 处理空矩阵后，取得行数和列数。
- 遍历左右边界，把其中的
O标记为#并加入队列。- 遍历上下边界，执行相同操作；四角因已被标记，不会重复入队。
- 不断出队并检查上下左右，相邻格为
O时立即标记并入队。- 扫描整个矩阵：把剩余
O改为X，把#恢复为O。例如经典矩阵中，内部相连的三个
O无法触边，最终被改成X；最下方边界上的O会在第一阶段被标记并恢复，所以保持不变。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
Deque<int[]> queue = new ArrayDeque<>();
for (int row = 0; row < rows; row++) {
offer(board, row, 0, queue);
offer(board, row, cols - 1, queue);
}
for (int col = 0; col < cols; col++) {
offer(board, 0, col, queue);
offer(board, rows - 1, col, queue);
}
while (!queue.isEmpty()) {
int[] cell = queue.pollFirst();
int row = cell[0];
int col = cell[1];
offer(board, row + 1, col, queue);
offer(board, row - 1, col, queue);
offer(board, row, col + 1, queue);
offer(board, row, col - 1, queue);
}
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
} else if (board[row][col] == '#') {
board[row][col] = 'O';
}
}
}
}
private void offer(char[][] board, int row, int col, Deque<int[]> queue) {
if (row < 0 || row >= board.length
|| col < 0 || col >= board[0].length
|| board[row][col] != 'O') {
return;
}
board[row][col] = '#';
queue.offerLast(new int[]{row, col});
}
}
func solve(board [][]byte) {
if len(board) == 0 || len(board[0]) == 0 {
return
}
rows, cols := len(board), len(board[0])
queue := make([][2]int, 0)
offer := func(row, col int) {
if row < 0 || row >= rows ||
col < 0 || col >= cols ||
board[row][col] != 'O' {
return
}
board[row][col] = '#'
queue = append(queue, [2]int{row, col})
}
for row := 0; row < rows; row++ {
offer(row, 0)
offer(row, cols-1)
}
for col := 0; col < cols; col++ {
offer(0, col)
offer(rows-1, col)
}
for head := 0; head < len(queue); head++ {
row, col := queue[head][0], queue[head][1]
offer(row+1, col)
offer(row-1, col)
offer(row, col+1)
offer(row, col-1)
}
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if board[row][col] == 'O' {
board[row][col] = 'X'
} else if board[row][col] == '#' {
board[row][col] = 'O'
}
}
}
}
复杂度分析
- 时间复杂度：$O(mn)$。每个格子至多被成功标记一次，最后再完整扫描一次矩阵。
- 空间复杂度：$O(mn)$。最坏情况下所有格子都与边界连通并进入队列；矩阵本身被原地复用，没有额外访问数组。
关键点总结
- 把「判断是否被包围」转成「从边界标记所有安全区域」，判定会简单很多。
- 安全性的单位是四连通块，不是单个格子。
#同时表示安全和已访问，避免额外空间。- 必须先标记当前格，再递归四个方向。
- 标记阶段和最终翻转阶段不能混在一起。
- 使用显式队列避免大连通块导致递归栈溢出，核心判据与 DFS 相同。
易错点总结
- 从内部
O正向搜索却不记录整块状态：一格触边意味着整个连通块都安全，不能逐格独立翻转。- 漏扫一条边：从该边连出的安全区域会被误翻转；左右边和上下边都要遍历。
- 把对角线算作连通：题目只允许上下左右四个方向。
- 出队后才标记：同一格可能被多个邻居重复加入队列；发现时就应标记。
- 只把
O改成X，忘记恢复#：输出会残留临时字符。- 恢复
#后又用独立if翻转O：应使用if ... else if，否则安全格会被再次改成X。- Go 每次用
queue = queue[1:]出队：功能正确但不便复用底层空间；使用递增的head下标更直接。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 连通块计数 |
| 463. 岛屿的周长 | 简单 | 逐格统计相邻水域边数 |
| 694. 不同岛屿的数量 | 中等 | 连通块形状序列化去重 |
| 695. 岛屿的最大面积 | 中等 | 连通块面积取最大值 |
| 1020. 飞地的数量 | 中等 | 边界反向标记后计数而非翻转 |
| 1254. 统计封闭岛屿的数目 | 中等 | 排除触边连通块后统计块数 |
| LCR 105. 岛屿的最大面积 | 中等 | 网格 DFS 回溯累加面积 |
| 面试题 16.19. 水域大小 | 中等 | 八连通连通块面积并排序输出 |