130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
- 连接：一个单元格与水平或垂直方向上相邻的单元格连接
- 区域：连接所有
'O' 的单元格来形成一个区域
- 围绕：如果您可以用
'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕
通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域
示例 1
输入：board = [[“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”]]
解释：
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕
示例 2
输入：board = [[“X”]]
输出：[[“X”]]
Solution 1
第一次尝试，使用深度优先搜索
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| class Solution {
public void solve(char[][] board) {
List<O> oList = new ArrayList<>();
Map<Integer, Map<Integer, O>> oMap = new HashMap<>();
O o;
for (int i = 0; i < board.length; i++) {
boolean topOrBottom = i == 0 || i == board.length - 1;
for (int j = 0, k = board[i].length; j < k; j++) {
if (board[i][j] != 'O') {
continue;
}
o = new O(i, j);
if (topOrBottom || j == 0 || j == k - 1) {
o.isBoard = true;
}
oList.add(o);
Map<Integer, O> jMap = oMap.computeIfAbsent(i, k1 -> new HashMap<>());
jMap.put(j, o);
}
}
Set<O> traveled = new HashSet<>();
for (O val : oList) {
if (val.isBoard && !traveled.contains(val)) {
traveled.add(val);
odfs(val, traveled, oMap);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0, k = board[i].length; j < k; j++) {
char c = board[i][j];
if (c == 'O' && !oMap.get(i).get(j).isBoard) {
board[i][j] = 'X';
}
}
}
}
private void odfs(O boardO, Set<O> traveled, Map<Integer, Map<Integer, O>> oMap) {
int x = boardO.getX();
int y = boardO.getY();
Map<Integer, O> x_s_1 = oMap.get(x - 1);
if (x_s_1 != null && x_s_1.get(y) != null && !traveled.contains(x_s_1.get(y))) {
O o = x_s_1.get(y);
o.isBoard = true;
traveled.add(o);
odfs(o, traveled, oMap);
}
Map<Integer, O> x_p_1 = oMap.get(x + 1);
if (x_p_1 != null && x_p_1.get(y) != null && !traveled.contains(x_p_1.get(y))) {
O o = x_p_1.get(y);
o.isBoard = true;
traveled.add(o);
odfs(o, traveled, oMap);
}
O o_s_1 = oMap.get(x).get(y - 1);
if (o_s_1 != null && !traveled.contains(o_s_1)) {
o_s_1.isBoard = true;
traveled.add(o_s_1);
odfs(o_s_1, traveled, oMap);
}
O o_p_1 = oMap.get(x).get(y + 1);
if (o_p_1 != null && !traveled.contains(o_p_1)) {
o_p_1.isBoard = true;
traveled.add(o_p_1);
odfs(o_p_1, traveled, oMap);
}
}
private static class O {
private int x;
private int y;
private boolean isBoard = false;
public O(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
return x == ((O) o).getX() && y == ((O) o).getY();
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
}
|
- 执行用时：14 ms（击败 5.10% 使用 Java 的用户）
- 内存消耗：45.14 MB（击败 10.36% 使用 Java 的用户）
Solution 2
核心逻辑不变，省略路径的记录，将遍历过的路径用特殊字符标记
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
| class Solution {
int xSize;
int ySize;
public void solve(char[][] board) {
xSize = board.length;
if (xSize == 0) {
return;
}
ySize = board[0].length;
for (int i = 0; i < xSize; i++) {
dfs(board, i, 0);
dfs(board, i, ySize - 1);
}
for (int i = 1; i < ySize - 1; i++) {
dfs(board, 0, i);
dfs(board, xSize - 1, i);
}
for (int i = 0; i < xSize; i++) {
for (int j = 0; j < ySize; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int x, int y) {
if (x < 0 || x >= xSize || y < 0 || y >= ySize || board[x][y] != 'O') {
return;
}
board[x][y] = 'A';
dfs(board, x - 1, y);
dfs(board, x + 1, y);
dfs(board, x, y - 1);
dfs(board, x, y + 1);
}
}
|
Source
130. 被围绕的区域
