0130. Surrounded Regions
=======================
题目信息
--------
:题号: 0130. 被围绕的区域
:难度: Medium
:主题: 网格、连通分量、多源广度优先搜索、原地标记
:原题: `LeetCode 0130 `_
:重点: 将“每个区域是否封闭”反转为“哪些 O 能从边界到达”,先保护安全补集再统一翻转
题目重述
--------
给定只含 ``'X'`` 和 ``'O'`` 的矩形网格 ``board``。上下左右相邻的 ``'O'`` 属于同一区域;一个区域只有
在其中所有格子都不位于边界时才被 ``'X'`` 完全围绕,需要把该区域的全部 ``'O'`` 原地改为 ``'X'``。
只要区域通过若干个 ``'O'`` 与任意边界格相连,整个区域都必须保留。
自建示例
--------
.. code-block:: text
输入: 修改后:
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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
void decideEveryComponent(std::vector>& board) {
const int rows = static_cast(board.size());
const int columns = static_cast(board[0].size());
const int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::vector> visited(
rows,
std::vector(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> pending;
std::vector> 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>& board) {
if (board.empty() || board[0].empty()) {
return;
}
const int rows = static_cast(board.size());
const int columns = static_cast(board[0].size());
const int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::queue> 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>& 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``,并且已经证明与边界连通”:
.. list-table::
:header-rows: 1
* - 搜索阶段字符
- 含义
- 最终动作
* - ``X``
- 原本就是阻挡格
- 保持 ``X``
* - ``O``
- 尚未证明安全;搜索结束仍为此状态即封闭
- 改为 ``X``
* - ``#``
- 已从边界到达的安全格
- 恢复为 ``O``
``protect`` 在入队时立即把 ``O`` 改为 ``#``。这样同一格子被不同邻居看到时,只有第一次能够入队;角点
虽然会被行边界循环和列边界循环各检查一次,也不会重复进入队列。若推迟到出队才标记,一个格子可能在
处理前被多个邻居重复加入。
具体走读空边界与内部通道
~~~~~~~~~~~~~~~~~~~~~~~~
在自建网格中,初始化边界时只有左下角一组中的底边 ``O`` 入队并变为 ``#``。BFS 向上找到与它相邻的
另一个 ``O``,也标成 ``#``;上方封闭区域与这条通道之间隔着 ``X``,始终保持 ``O``。最终扫描将上方
四格翻为 ``X``,把两个 ``#`` 恢复为 ``O``。
若网格只有一行或一列,每个格子都在边界上。所有 ``O`` 会在初始化或随后的扩展中变为 ``#``,最终全部
恢复,因此自然得到“没有被围绕区域”,无需尺寸特判。空网格检查则必须发生在读取 ``board[0]`` 之前。
正确性、主解选择与复杂度
~~~~~~~~~~~~~~~~~~~~~~~~
从边界多源 BFS 标记的每个格子,都有一条由搜索父关系构成的 ``O`` 路径连接边界,所以确实不能翻转;
任意应保留的 ``O`` 也有这样一条路径,BFS 会从路径的边界端逐格到达它,所以不会漏标。于是未标记 ``O``
与“被围绕区域”完全相同,最终转换正确。
公开入口采用边界反向搜索:它和逐分量方案都是 ``O(mn)`` 时间,却利用网格字符原地记录访问状态,只需
队列最坏 ``O(mn)`` 空间,不再分配访问矩阵和分量列表。逐分量方案保留为直觉演进,因为它直接表达原始
判定;多源方案则把“先收集、后决定”变成“先保护、再翻转补集”。