05 August 2008
给定一个 m x n 整数矩阵网格，以及三个整数 row、col 和 color。网格中的每个值代表该位置的网格正方形的颜色。
如果两个正方形具有相同的颜色并且在 4 个方向中的任何一个方向上彼此相邻，则它们属于同一个连通分量。
连通分量的边界是连通分量中的所有正方形，这些正方形与不在该分量中的正方形在 4 方向上相邻，或者在网格的边界（第一行或最后一行或列）上。
您应该使用颜色为包含方形 grid[row][col] 的连接组件的边框着色。
返回最终网格。
DFS
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
class Solution {
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int rows = grid.length;
int columns = grid[0].length;
int startPositionValue = grid[row][col];
List<List<Integer>> list = new ArrayList<List<Integer>>();
boolean[][] visited = new boolean[rows][columns];
dfs(grid, row, col, rows, columns, startPositionValue, visited, list);
for (List<Integer> integers : list) {
grid[integers.get(0)][integers.get(1)] = color;
}
return grid;
}
private void dfs(int[][] grid, int x, int y, int rows, int columns,
int startPositionValue, boolean[][] visited, List<List<Integer>> list) {
if (x < 0 || x >= rows || y < 0 || y >= columns || visited[x][y] || grid[x][y] != startPositionValue)
return;
visited[x][y] = true;
if (boundary(grid, x, y, rows, columns, startPositionValue)) {
list.add(new ArrayList<>(Arrays.asList(x, y)));
}
dfs(grid, x + 1, y, rows, columns, startPositionValue, visited, list);
dfs(grid, x - 1, y, rows, columns, startPositionValue, visited, list);
dfs(grid, x, y + 1, rows, columns, startPositionValue, visited, list);
dfs(grid, x, y - 1, rows, columns, startPositionValue, visited, list);
}
private boolean boundary(int[][] grid, int x, int y, int rows, int columns, int startPositionValue) {
if (x == 0 || x == rows - 1 || y == 0 || y == columns - 1)
return true;
int count = 0;
if (grid[x - 1][y] == startPositionValue)
count++;
if (grid[x][y + 1] == startPositionValue)
count++;
if (grid[x + 1][y] == startPositionValue)
count++;
if (grid[x][y - 1] == startPositionValue)
count++;
return count != 4;
}
}
BFS
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
class Solution {
public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
boolean[][] border = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r0, c0});
visited[r0][c0] = true; // visited
int[][] steps = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
//System.out.println("now to bfs");
while (!queue.isEmpty()) {
int[] item = queue.poll();
int x = item[0];
int y = item[1];
//System.out.println("x=" + x + ", y=" + y);
for (int[] step : steps) {
int nextx = x + step[0];
int nexty = y + step[1];
if (nextx < 0 || nextx >= rows || nexty < 0 || nexty >= cols || grid[nextx][nexty] != grid[x][y]) {
border[x][y] = true; // is border
} else { // so here, next color is the same
if (!visited[nextx][nexty]) { // not visited
queue.add(new int[]{nextx, nexty});
visited[nextx][nexty] = true;
}
}
}
}
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[i].length; ++j) {
if (border[i][j]) {
grid[i][j] = color;
}
}
}
return grid;
}
}