题目描述
先确认输入、输出、限制条件，再判断能不能把暴力解法优化掉。
思路解析动画文字版
关键转折：思路一句话：别判「谁被围」，反过来从四条边的 O 出发染绿保护，剩下没染到的 O 必定被围、统统变 X。下面一步步演给你看。
第 1 步 · 找出所有边界上的 O：网格四条边上一共有 1 个 O（橙色），它们挨着边界、绝不会被围。接下来从每一个这样的 O 出发做 DFS，把和它相连的 O 一路染成绿色「安全」。X（灰）是墙，染色绕不过去。
DFS 起步 · 边界 O (0,0) 入栈：从边界上的 O (0,0) 开始一趟 DFS。它本身就挨着边，铁定安全 —— 标成绿色，然后顺着它的 O 邻居继续往里钻。
DFS 扩散 · 相连的 O (1,0) 染安全：从 (0,0) 顺到相连的 O (1,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(1,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (2,0) 染安全：从 (1,0) 顺到相连的 O (2,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(2,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (3,0) 染安全：从 (2,0) 顺到相连的 O (3,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(3,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (4,0) 染安全：从 (3,0) 顺到相连的 O (4,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (4,1) 染安全：从 (4,0) 顺到相连的 O (4,1)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,1) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (0,1) 染安全：从 (0,0) 顺到相连的 O (0,1)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,1) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (0,2) 染安全：从 (0,1) 顺到相连的 O (0,2)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,2) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (0,3) 染安全：从 (0,2) 顺到相连的 O (0,3)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,3) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (0,4) 染安全：从 (0,3) 顺到相连的 O (0,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (1,4) 染安全：从 (0,4) 顺到相连的 O (1,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(1,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (2,4) 染安全：从 (1,4) 顺到相连的 O (2,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(2,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (3,4) 染安全：从 (2,4) 顺到相连的 O (3,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(3,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (4,4) 染安全：从 (3,4) 顺到相连的 O (4,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
DFS 扩散 · 相连的 O (4,3) 染安全：从 (4,4) 顺到相连的 O (4,3)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,3) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
边界 DFS 跑完 · 揪出被围的 O：所有从边界能连到的 O 都染绿了。现在扫一遍整张图：还是 O、又没被染绿的格子（红色）就是被四面 X 围死、连不到边界的 —— 它们就是要翻成 X 的「被围区域」。本例是 (2,2) (3,2)。
翻牌 · 被围 O (2,2) → X：(2,2) 没被边界染到，确认被围 —— 翻成 X。被围的 O 是真的被困住了：它的四个方向要么是 X、要么是同样被困的 O，怎么都连不到边界。
翻牌 · 被围 O (3,2) → X：(3,2) 没被边界染到，确认被围 —— 翻成 X。被围的 O 是真的被困住了：它的四个方向要么是 X、要么是同样被困的 O，怎么都连不到边界。
完成 · 安全 O 保留、被围 O 全变 X：最终结果：绿色那片 O 因为连着边界被原样保留，被围那几格变成了 X。一句话总结整道题 —— 与边界相连的 O 永远不会被围；先从四边的 O 染色保护，剩下没染到的 O 就是被围的，变 X。
边界：空网格直接返回；整张全是 O 时全部都连边界、一个都不翻；只有一行或一列时所有格都在边界上，同样全安全。被四面围死的单格 O 是最典型的要翻对象。
高频追问：问：为什么不直接判断每个 O 是否被围？答：一片 O 的「是否被围」是整体性质，单格判断要反复扩展同一片、很费；从边界反向标安全一次就把所有安全 O 标完。问：DFS 递归爆栈怎么办？答：改成显式栈或并查集，逻辑等价。
参考代码
def solve(board): if not board: return R, C = len(board), len(board[0]) def dfs(i, j): if i < 0 or j < 0 or i >= R or j >= C: return if board[i][j] != "O": return board[i][j] = "#" # 标安全 dfs(i+1, j); dfs(i-1, j) dfs(i, j+1); dfs(i, j-1) for i in range(R): # 从四条边的 O 出发 for j in range(C): if (i in (0, R-1) or j in (0, C-1)) \ and board[i][j] == "O": dfs(i, j) for i in range(R): for j in range(C): if board[i][j] == "O": board[i][j] = "X" elif board[i][j] == "#": board[i][j] = "O"复杂度
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
腐烂的橘子
LeetCode 994 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题