题目描述
130. 被围绕的区域
难度中等
给定一个二维的矩阵,包含 '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'
。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
相关题目
Floodfill算法相关的题,这题和第1254题几乎一样。
题目本身题目不算难,但是自己写了两遍换了横纵的字母第二遍的时候一直通不过,吭哧哼哧花了好久找错,结果发现栽在一个小地方。写下题解留个纪念。
Floodfill 相关的题目有:
200. Number of Islands 岛屿数量
695. Max Area of Island 岛屿的最大面积
1254. Number of Closed Islands 统计封闭岛屿的数目
130. Surrounded Regions 被围绕的区域
934. Shortest Bridge 最短的桥
写法1
(Floodfill) $O(n^2)$
思路:逆向思维,由于是封闭区域,那么周围一圈里的 'O'
即便找到了它们的连通块也不能看作封闭区域,所以要排除。
先统计无需变成 'X'
的区域,然后将其它区域都变成 'X'
即可。
- 统计无需变成
'X'
的区域: 搜索周围一圈找到'O'
及其连通块,然后标记为'#'
- 再总的扫描一遍将所有未标记的
'O'
的位置变为'X'
时间复杂度
每个位置仅被遍历一次,所以时间复杂度是 $O(n^2)$,其中 n
是地图的边长。
C++ 代码
class Solution {
public:
int m, n;
vector<int> dirs{0, 1, 0, -1, 0};
void solve(vector<vector<char>>& board) {
m = board.size();
if (!m) return;
n = board[0].size();
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == '#') board[i][j] = 'O';
else board[i][j] = 'X';
}
void dfs(vector<vector<char>>& board, int x, int y) {
board[x][y] = '#';
for (int k = 0; k < 4; k++) {
int a = x + dirs[k], b = y + dirs[k + 1];
if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O')
dfs(board, a, b);
}
}
};
写法2 更简洁
C++ 代码
class Solution {
public:
int m, n;
vector<int> dirs{0, 1, 0, -1, 0};
void solve(vector<vector<char>>& board) {
m = board.size();
if (!m) return;
n = board[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1))
dfs(board, i, j);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == '#') board[i][j] = 'O';
else board[i][j] = 'X';
}
void dfs(vector<vector<char>>& board, int x, int y) {
board[x][y] = '#';
for (int k = 0; k < 4; k++) {
int a = x + dirs[k], b = y + dirs[k + 1];
if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O')
dfs(board, a, b);
}
}
};
可以把中间的两段代码合并一下,减少工作量:
原来的代码:
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
}
合并后的代码:
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1))
dfs(board, i, j);
}