题目链接

图像渲染

题目描述

image.png
image.png

实现代码

基于栈采用BFS广度优先遍历方式实现代码如下（结果超时）：

  1. class Solution {
  2.     public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
  4.         int m = image.length;
  5.         int n = image[0].length;
  7.         Stack<Integer> stackX = new Stack<>();
  8.         Stack<Integer> stackY = new Stack<>();
  10.         stackX.add(sr);
  11.         stackY.add(sc);
  13.         int oldColor = image[sr][sc];
  14.         image[sr][sc] = newColor;
  15.         while (!stackX.isEmpty()) {
  16.             int x = stackX.pop();
  17.             int y = stackY.pop();
  19.             if(x+1 < m && image[x+1][y] == oldColor) {
  20.                 stackX.add(x+1);
  21.                 stackY.add(y);
  22.                 image[x+1][y] = newColor;
  23.             }
  24.             if(x-1 >= 0 && image[x-1][y] == oldColor) {
  25.                 stackX.add(x-1);
  26.                 stackY.add(y);
  27.                 image[x-1][y] = newColor;
  28.             }
  29.             if(y+1 < n && image[x][y+1] == oldColor) {
  30.                 stackX.add(x);
  31.                 stackY.add(y+1);
  32.                 image[x][y+1] = newColor;
  33.             }
  34.             if(y-1 >= 0 && image[x][y-1] == oldColor) {
  35.                 stackX.add(x);
  36.                 stackY.add(y-1);
  37.                 image[x][y-1] = newColor;
  38.             }
  39.         }
  40.         return image;
  41.     }
  42. }

基于队列采用BFS广度优先遍历实现代码如下（结果居然没超时，离谱）：

  1. class Solution {
  2.     int[] dx = {1, 0, 0, -1};
  3.     int[] dy = {0, 1, -1, 0};
  5.     public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
  6.         int currColor = image[sr][sc];
  7.         if (currColor == newColor) {
  8.             return image;
  9.         }
  10.         int n = image.length, m = image[0].length;
  11.         Queue<int[]> queue = new LinkedList<int[]>();
  12.         queue.offer(new int[]{sr, sc});
  13.         image[sr][sc] = newColor;
  14.         while (!queue.isEmpty()) {
  15.             int[] cell = queue.poll();
  16.             int x = cell[0], y = cell[1];
  17.             for (int i = 0; i < 4; i++) {
  18.                 int mx = x + dx[i], my = y + dy[i];
  19.                 if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
  20.                     queue.offer(new int[]{mx, my});
  21.                     image[mx][my] = newColor;
  22.                 }
  23.             }
  24.         }
  25.         return image;
  26.     }
  27. }

采用DFS深度优先遍历实现代码如下：

  1. class Solution {
  2.     int[] dx = {1, 0, 0, -1};
  3.     int[] dy = {0, 1, -1, 0};
  5.     public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
  6.         int currColor = image[sr][sc];
  7.         if (currColor != newColor) {
  8.             dfs(image, sr, sc, currColor, newColor);
  9.         }
  10.         return image;
  11.     }
  13.     public void dfs(int[][] image, int x, int y, int color, int newColor) {
  14.         if (image[x][y] == color) {
  15.             image[x][y] = newColor;
  16.             for (int i = 0; i < 4; i++) {
  17.                 int mx = x + dx[i], my = y + dy[i];
  18.                 if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
  19.                     dfs(image, mx, my, color, newColor);
  20.                 }
  21.             }
  22.         }
  23.     }
  24. }