题目链接
题目描述
实现代码
基于栈采用BFS广度优先遍历方式实现代码如下(结果超时):
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int m = image.length;
int n = image[0].length;
Stack<Integer> stackX = new Stack<>();
Stack<Integer> stackY = new Stack<>();
stackX.add(sr);
stackY.add(sc);
int oldColor = image[sr][sc];
image[sr][sc] = newColor;
while (!stackX.isEmpty()) {
int x = stackX.pop();
int y = stackY.pop();
if(x+1 < m && image[x+1][y] == oldColor) {
stackX.add(x+1);
stackY.add(y);
image[x+1][y] = newColor;
}
if(x-1 >= 0 && image[x-1][y] == oldColor) {
stackX.add(x-1);
stackY.add(y);
image[x-1][y] = newColor;
}
if(y+1 < n && image[x][y+1] == oldColor) {
stackX.add(x);
stackY.add(y+1);
image[x][y+1] = newColor;
}
if(y-1 >= 0 && image[x][y-1] == oldColor) {
stackX.add(x);
stackY.add(y-1);
image[x][y-1] = newColor;
}
}
return image;
}
}
基于队列采用BFS广度优先遍历实现代码如下(结果居然没超时,离谱):
class Solution {
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];
if (currColor == newColor) {
return image;
}
int n = image.length, m = image[0].length;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{sr, sc});
image[sr][sc] = newColor;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
queue.offer(new int[]{mx, my});
image[mx][my] = newColor;
}
}
}
return image;
}
}
采用DFS深度优先遍历实现代码如下:
class Solution {
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];
if (currColor != newColor) {
dfs(image, sr, sc, currColor, newColor);
}
return image;
}
public void dfs(int[][] image, int x, int y, int color, int newColor) {
if (image[x][y] == color) {
image[x][y] = newColor;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
dfs(image, mx, my, color, newColor);
}
}
}
}
}