05 August 2008
图像渲染，相邻的四个方向按跟现在的值相等的情况下修改成新值，从而完成渲染
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
class Solution {
private final int[][] dirs = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} }; //上左右下
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if (image == null || image.length == 0 || image[0].length == 0) {
return new int[0][0];
}
int rows = image.length;
int cols = image[0].length;
boolean[][] visited = new boolean[rows][cols];
Deque<int[]> queue = new ArrayDeque<>(); // Queue是interface，Deque extend queue也是interface，可以用LinkedList或ArrayDeque
queue.offer(new int[]{sr, sc});
visited[sr][sc] = true;
while (!queue.isEmpty()) {
// int size = queue.size();
int[] curr = queue.poll();
int currValue = image[curr[0]][curr[1]]; //记录当前的颜色值方便与四边比较
image[curr[0]][curr[1]] = newColor;
for (int[] dir : dirs) {
int newX = curr[0] + dir[0];
int newY = curr[1] + dir[1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited[newX][newY] && image[newX][newY] == currValue) {
visited[newX][newY] = true;
queue.offer(new int[]{newX, newY});
}
}
}
return image;
}
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int rows = image.length;
int cols = image[0].length;
dfs(image, sr, sc, newColor, image[sr][sc], rows, cols);
return image;
}
public void dfs(int[][] image, int x, int y, int newColor, int oldColor, int rows, int cols) {
if (x < 0 || x >= rows || y < 0 || y >= cols || image[x][y] == newColor || image[x][y] != oldColor) {
return;
}
image[x][y] = newColor;
dfs(image, x + 1, y, newColor, oldColor, rows, cols);
dfs(image, x - 1, y, newColor, oldColor, rows, cols);
dfs(image, x, y + 1, newColor, oldColor, rows, cols);
dfs(image, x, y - 1, newColor, oldColor, rows, cols);
}
}