第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0130. 被围绕的区域

题目地址(130. 被围绕的区域)

题目描述

1
给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。
2
3
找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。
4
5
示例:
6
7
X X X X
8
X O O X
9
X X O X
10
X O X X
11
运行你的函数后,矩阵变为:
12
13
X X X X
14
X X X X
15
X X X X
16
X O X X
17
解释:
18
19
被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
Copied!

前置知识

  • DFS

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

我们需要将所有被 X 包围的 O 变成 X,并且题目明确说了边缘的所有 O 都是不可以变成 X 的。
130.surrounded-regions
其实我们观察会发现,我们除了边缘的 O 以及和边缘 O 连通的 O 是不需要变成 X 的,其他都要变成 X。
经过上面的思考,问题转化为连通区域问题。 这里我们需要标记一下边缘的O以及和边缘O连通的O。 我们当然可以用额外的空间去存,但是对于这道题目而言,我们完全可以 mutate。这样就空间复杂度会好一点。
整个过程如图所示:
我将边缘的O以及和边缘O连通的O 标记为了 "A"
130.surrounded-regions

关键点解析

  • 二维数组 DFS 解题模板
  • 转化问题为连通区域问题
  • 直接 mutate 原数组,节省空间

代码

  • 语言支持:JS,Python3, CPP
1
/*
2
* @lc app=leetcode id=130 lang=javascript
3
*
4
* [130] Surrounded Regions
5
*/
6
// 将O以及周边的O转化为A
7
function mark(board, i, j, rows, cols) {
8
if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O")
9
return;
10
11
board[i][j] = "A";
12
mark(board, i + 1, j, rows, cols);
13
mark(board, i - 1, j, rows, cols);
14
mark(board, i, j + 1, rows, cols);
15
mark(board, i, j - 1, rows, cols);
16
}
17
/**
18
* @param {character[][]} board
19
* @return {void} Do not return anything, modify board in-place instead.
20
*/
21
var solve = function (board) {
22
const rows = board.length;
23
if (rows === 0) return [];
24
const cols = board[0].length;
25
26
for (let i = 0; i < rows; i++) {
27
for (let j = 0; j < cols; j++) {
28
if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1) {
29
mark(board, i, j, rows, cols);
30
}
31
}
32
}
33
34
for (let i = 0; i < rows; i++) {
35
for (let j = 0; j < cols; j++) {
36
if (board[i][j] === "O") {
37
board[i][j] = "X";
38
} else if (board[i][j] === "A") {
39
board[i][j] = "O";
40
}
41
}
42
}
43
44
return board;
45
};
Copied!
Python Code:
1
class Solution:
2
def solve(self, board: List[List[str]]) -> None:
3
"""
4
Do not return anything, modify board in-place instead.
5
"""
6
# 如果数组长或宽小于等于2,则不需要替换
7
if len(board) <= 2 or len(board[0]) <= 2:
8
return
9
10
row, col = len(board), len(board[0])
11
12
def dfs(i, j):
13
"""
14
深度优先算法,如果符合条件,替换为A并进一步测试,否则停止
15
"""
16
if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O':
17
return
18
board[i][j] = 'A'
19
20
dfs(i - 1, j)
21
dfs(i + 1, j)
22
dfs(i, j - 1)
23
dfs(i, j + 1)
24
25
# 从外围开始
26
for i in range(row):
27
dfs(i, 0)
28
dfs(i, col-1)
29
30
for j in range(col):
31
dfs(0, j)
32
dfs(row-1, j)
33
34
# 最后完成替换
35
for i in range(row):
36
for j in range(col):
37
if board[i][j] == 'O':
38
board[i][j] = 'X'
39
elif board[i][j] == 'A':
40
board[i][j] = 'O'
Copied!
CPP Code:
1
class Solution {
2
int M, N, dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
3
void dfs(vector<vector<char>> &board, int x, int y) {
4
if (x < 0 || x >= M || y < 0 || y >= N || board[x][y] != 'O') return;
5
board[x][y] = '#';
6
for (auto &dir : dirs) dfs(board, x + dir[0], y + dir[1]);
7
}
8
public:
9
void solve(vector<vector<char>>& board) {
10
if (board.empty() || board[0].empty()) return;
11
M = board.size(), N = board[0].size();
12
for (int i = 0; i < M; ++i) {
13
dfs(board, i, 0);
14
dfs(board, i, N - 1);
15
}
16
for (int j = 0; j < N; ++j) {
17
dfs(board, 0, j);
18
dfs(board, M - 1, j);
19
}
20
for (auto &row : board) {
21
for (auto &cell : row) {
22
cell = cell == '#' ? 'O' : 'X';
23
}
24
}
25
}
26
};
Copied!

相关题目

解题模板是一样的
复杂度分析
  • 时间复杂度:$O(row * col)$
  • 空间复杂度:$O(row * col)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。