leetcode 130. 被围绕的区域
题目：130. 被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
输出: 2
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
**解释: **
- 被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。
- 如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
方法：DFS（深度优先搜索）
思路：DFS（深度优先搜索），通过DFS将所有没有被 ‘X’ 围绕的区域的所有’O’修改为’T’，此时矩阵中剩余的’O’都是被’X’ 围绕的，然后通过遍历矩阵将所有的’O’修改为’X’,将所有的’T’修改为’O’,即可得到所求结果。
运行数据：执行用时：2 ms，内存消耗：41.9 MB
复杂度分析：
- 时间复杂度：O(n * m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
- 空间复杂度：O(n * m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
dfs(board, 0, i);
}
if (board[m - 1][i] == 'O') {
dfs(board, m - 1, i);
}
}
for (int i = 1; i < m - 1; i++) {
if (board[i][0] == 'O') {
dfs(board, i, 0);
}
if (board[i][n - 1] == 'O') {
dfs(board, i, n - 1);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int a, int b) {
if (a < 0 || b < 0 || a >= board.length || b >= board[0].length || board[a][b] != 'O') {
return ;
}
board[a][b] = 'T';
dfs(board, a + 1, b);
dfs(board, a - 1, b);
dfs(board, a, b + 1);
dfs(board, a, b - 1);
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
