0130. Surrounded Regions¶
题目信息¶
- 题号:
被围绕的区域
- 难度:
Medium
- 主题:
网格、连通分量、多源广度优先搜索、原地标记
- 原题:
- 重点:
将“每个区域是否封闭”反转为“哪些 O 能从边界到达”,先保护安全补集再统一翻转
题目重述¶
给定只含 'X' 和 'O' 的矩形网格 board。上下左右相邻的 'O' 属于同一区域;一个区域只有
在其中所有格子都不位于边界时才被 'X' 完全围绕,需要把该区域的全部 'O' 原地改为 'X'。
只要区域通过若干个 'O' 与任意边界格相连,整个区域都必须保留。
自建示例¶
输入: 修改后:
X X X X X X X X X X
X O O X X X X X X X
X X O O X X X X X X
X O X X X X O X X X
X O X X X X O X X X
上方四个 O 组成封闭区域;左下两个 O 与底边相连,即使其中一个不在边界也必须保留。
单行网格 [O, X, O, O] 中每个位置都属于边界,因此没有任何 O 可以翻转。
C++ 实现¶
#include <queue>
#include <utility>
#include <vector>
class Solution {
private:
void decideEveryComponent(std::vector<std::vector<char>>& board) {
const int rows = static_cast<int>(board.size());
const int columns = static_cast<int>(board[0].size());
const int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::vector<std::vector<bool>> visited(
rows,
std::vector<bool>(columns, false)
);
for (int startRow = 0; startRow < rows; ++startRow) {
for (int startColumn = 0; startColumn < columns; ++startColumn) {
if (board[startRow][startColumn] != 'O' ||
visited[startRow][startColumn]) {
continue;
}
std::queue<std::pair<int, int>> pending;
std::vector<std::pair<int, int>> component;
pending.push({startRow, startColumn});
visited[startRow][startColumn] = true;
bool touchesBoundary = false;
while (!pending.empty()) {
auto [row, column] = pending.front();
pending.pop();
component.push_back({row, column});
if (row == 0 || row == rows - 1 ||
column == 0 || column == columns - 1) {
touchesBoundary = true;
}
for (const auto& direction : directions) {
const int nextRow = row + direction[0];
const int nextColumn = column + direction[1];
if (nextRow < 0 || nextRow >= rows ||
nextColumn < 0 || nextColumn >= columns ||
board[nextRow][nextColumn] != 'O' ||
visited[nextRow][nextColumn]) {
continue;
}
visited[nextRow][nextColumn] = true;
pending.push({nextRow, nextColumn});
}
}
if (!touchesBoundary) {
for (auto [row, column] : component) {
board[row][column] = 'X';
}
}
}
}
}
void protectBoundaryComponents(std::vector<std::vector<char>>& board) {
if (board.empty() || board[0].empty()) {
return;
}
const int rows = static_cast<int>(board.size());
const int columns = static_cast<int>(board[0].size());
const int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::queue<std::pair<int, int>> pending;
auto protect = [&](int row, int column) {
if (board[row][column] == 'O') {
board[row][column] = '#';
pending.push({row, column});
}
};
for (int row = 0; row < rows; ++row) {
protect(row, 0);
protect(row, columns - 1);
}
for (int column = 0; column < columns; ++column) {
protect(0, column);
protect(rows - 1, column);
}
while (!pending.empty()) {
auto [row, column] = pending.front();
pending.pop();
for (const auto& direction : directions) {
const int nextRow = row + direction[0];
const int nextColumn = column + direction[1];
if (nextRow >= 0 && nextRow < rows &&
nextColumn >= 0 && nextColumn < columns) {
protect(nextRow, nextColumn);
}
}
}
for (auto& row : board) {
for (char& cell : row) {
if (cell == 'O') {
cell = 'X';
} else if (cell == '#') {
cell = 'O';
}
}
}
}
public:
void solve(std::vector<std::vector<char>>& board) {
protectBoundaryComponents(board);
}
};
题解¶
原始问题为何容易产生重复搜索¶
对一个内部 O,最直接的问题是:“从这里沿 O 能否走到边界?”可以为每个格子单独做 DFS 或 BFS,
但同一区域中的每个起点都会重新走过几乎相同的格子;在一大片 O 中,搜索量可能从网格大小
mn 膨胀到 O((mn)^2)。而且在确定无法到边界之前不能提前翻转途中的格子,否则后续搜索看到的图已
被改变。
方案一:以连通分量为单位作决定¶
decideEveryComponent 使用全局 visited,每个未访问 O 只启动一次 BFS。搜索时同时收集
component,并记录是否碰到任意边界;完成整个分量后,只有 touchesBoundary == false 才统一翻转。
这个方案把逐格重复判断压缩为逐分量判断,每个格子只搜索一次,时间已是 O(mn)。不过每个分量仍需
保存格子列表,等到“是否接触边界”确定后再决定是否回写;还要同时维护 visited 和原网格两套状态。
结构反转:应翻转集合的补集更容易找到¶
一个区域“不被围绕”当且仅当它含有边界 O。等价地,一个 O 应被保留,当且仅当存在一条全由
O 组成的四方向路径把它连接到边界。所有安全格子因此可以从四条边上的 O 同时出发,一次连通搜索
直接得到;搜索结束后仍未标记的 O 恰好就是封闭区域。
这使算法不再为每个分量记录一个布尔结论和完整成员列表,而是先给安全补集打标记,最后对全网格做一次 确定性转换。
三种字符就是三个阶段状态¶
输入只允许 X 和 O,所以搜索期间可借用 # 表示“原本是 O,并且已经证明与边界连通”:
搜索阶段字符 |
含义 |
最终动作 |
|---|---|---|
|
原本就是阻挡格 |
保持 |
|
尚未证明安全;搜索结束仍为此状态即封闭 |
改为 |
|
已从边界到达的安全格 |
恢复为 |
protect 在入队时立即把 O 改为 #。这样同一格子被不同邻居看到时,只有第一次能够入队;角点
虽然会被行边界循环和列边界循环各检查一次,也不会重复进入队列。若推迟到出队才标记,一个格子可能在
处理前被多个邻居重复加入。
具体走读空边界与内部通道¶
在自建网格中,初始化边界时只有左下角一组中的底边 O 入队并变为 #。BFS 向上找到与它相邻的
另一个 O,也标成 #;上方封闭区域与这条通道之间隔着 X,始终保持 O。最终扫描将上方
四格翻为 X,把两个 # 恢复为 O。
若网格只有一行或一列,每个格子都在边界上。所有 O 会在初始化或随后的扩展中变为 #,最终全部
恢复,因此自然得到“没有被围绕区域”,无需尺寸特判。空网格检查则必须发生在读取 board[0] 之前。
正确性、主解选择与复杂度¶
从边界多源 BFS 标记的每个格子,都有一条由搜索父关系构成的 O 路径连接边界,所以确实不能翻转;
任意应保留的 O 也有这样一条路径,BFS 会从路径的边界端逐格到达它,所以不会漏标。于是未标记 O
与“被围绕区域”完全相同,最终转换正确。
公开入口采用边界反向搜索:它和逐分量方案都是 O(mn) 时间,却利用网格字符原地记录访问状态,只需
队列最坏 O(mn) 空间,不再分配访问矩阵和分量列表。逐分量方案保留为直觉演进,因为它直接表达原始
判定;多源方案则把“先收集、后决定”变成“先保护、再翻转补集”。