2020.8.11 每日题解 LeetCode 130. 被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
1
2
3
4
| X X X X
X O O X
X X O X
X O X X
|
运行你的函数后，矩阵变为：
1
2
3
4
| X X X X
X X X X
X X X X
X O X X
|
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
思路详解
通过题干可知，问题实际上要找到的其实是和边界上的’O’间接或者直接相连的’O’。
即可利用DFS在四条边界上进行寻找符合题意的’O’标注为’S’,最后将二维数组中的’S’变为’O’,’O’变为’X’即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class M130_SroundingArea {
public void solve(char[][] board) {
if (board.length == 0)
return;
int l = board.length;
int l2 = board[0].length;
if (l == 1 || l2 == 1 || l == 2 || l2 == 2)
return;
for (int i = 0; i < l2; i++) {
board = dfs(board, 0, i);
board = dfs(board, l - 1, i);
}
for (int i = 0; i < l; i++) {
board = dfs(board, i, 0);
board = dfs(board, i, l2 - 1);
}
for (int i = 0; i < l; i++) {
for (int j = 0; j < l2; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'S') board[i][j] = 'O';
}
}
}
public char[][] dfs(char[][] board, int i, int j) {
if (i >= 0 && j >= 0 && i < board.length && j < board[0].length && board[i][j] == 'O') {
board[i][j] = 'S';
dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
}
return board;
}
}
|
PS：感觉可以用记忆化来降低时间复杂度，但是会增加一个O(i,j)的访问数组造成空间损耗
