LeetCode 733：圖像渲染 flood-fill

2019 年 10 月 5 日
筆記

題目：

有一幅以二維整數數組表示的圖畫，每一個整數表示該圖畫的像素值大小，數值在 0 到 65535 之間。

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

給你一個坐標 (sr, sc) 表示圖像渲染開始的像素值（行，列）和一個新的顏色值 newColor，讓你重新上色這幅圖像。

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

為了完成上色工作，從初始坐標開始，記錄初始坐標的上下左右四個方向上像素值與初始坐標相同的相連像素點，接着再記錄這四個方向上符合條件的像素點與他們對應四個方向上像素值與初始坐標相同的相連像素點，……，重複該過程。將所有有記錄的像素點的顏色值改為新的顏色值。

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

最後返回經過上色渲染後的圖像。

At the end, return the modified image.

示例 1:

輸入:  image = [[1,1,1],[1,1,0],[1,0,1]]  sr = 1, sc = 1, newColor = 2  輸出: [[2,2,2],[2,2,0],[2,0,1]]  解析:  在圖像的正中間，(坐標(sr,sc)=(1,1)),  在路徑上所有符合條件的像素點的顏色都被更改成2。  注意，右下角的像素沒有更改為2，  因為它不是在上下左右四個方向上與初始點相連的像素點。

注意:

image 和 image[0] 的長度在範圍 [1, 50] 內。
給出的初始點將滿足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的顏色值在範圍 [0, 65535]內。

Note:

The length of image and image[0] will be in the range [1, 50].

The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.

The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

解題思路：

與01矩陣類似，在圖的數據結構內找到所有舊的像素點改成新的新素值。無非是圖的遍歷，BFS和DFS。

就這道題而言，不涉及路徑長度，明顯DFS深度優先遍歷更適合。因為BFS廣度優先遍歷需要記錄每個相鄰符合要求的位置，並且不能添加重複的點。 DFS可以用棧或遞歸實現，如果用棧來解雖然比遞歸更好理解一些，但是每次依然要存儲每個點的索引位置，並且出入棧也會消耗時間。所以這道題的最優解應該是用遞歸實現的深度優先遍歷解題。

代碼：

DFS（Java）：

class Solution {      private boolean withinBounds(int[][] img, int i, int j) {//判斷指針是否溢出          return (i < img.length && i >= 0) && (j < img[0].length && j >= 0);      }        private void floodFillProcess(int[][] img, int sr, int sc, int oc, int nc) {          if (withinBounds(img, sr, sc) && img[sr][sc] == oc) {//指針不溢出且像素值為舊值時              img[sr][sc] = nc;//改為新值              floodFillProcess(img, sr - 1, sc, oc, nc);//遞歸上下左右四個點              floodFillProcess(img, sr + 1, sc, oc, nc);              floodFillProcess(img, sr, sc - 1, oc, nc);              floodFillProcess(img, sr, sc + 1, oc, nc);          }      }        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {          int oc = image[sr][sc];          if (newColor == oc) return image;          floodFillProcess(image, sr, sc, oc, newColor);          return image;      }  }

DFS（Python）：

class Solution:      def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:          oldColor = image[sr][sc]          if oldColor == newColor:              return image          self.dfs(image, sr, sc, oldColor, newColor)          return image        def dfs(self, image: List[List[int]], sr: int, sc: int, oldColor: int, newColor: int):          if image[sr][sc] == oldColor:              image[sr][sc] = newColor              if sr-1 >= 0:#先判斷是否溢出再決定是否遞歸                  self.dfs(image, sr-1, sc, oldColor, newColor)              if sr+1 < len(image):                  self.dfs(image, sr+1, sc, oldColor, newColor)              if sc-1 >= 0:                  self.dfs(image, sr, sc-1, oldColor, newColor)              if sc+1 < len(image[0]):                  self.dfs(image, sr, sc+1, oldColor, newColor)

附：

BFS深度優先遍歷(Java):

class Solution {      public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {          int oldColor = image[sr][sc];          if (oldColor == newColor) return image;//舊像素值與新像素值相等時，無需修改          int rows = image.length;          int columns = image[0].length;          bfs(image, sr * columns + sc, rows, columns, newColor, oldColor);//進入BFS輔助函數          return image;      }        private void bfs(int[][] img, int loc, int row, int column, int nc, int oc) {          Set<Integer> set = new LinkedHashSet<>(); //set(),避免添加重複點          Queue<Integer> queue = new LinkedList<>();          queue.add(loc);//隊列加入第一個初始點，記錄點索引的方式是x*column+y，          while (!queue.isEmpty()) {              int tmp = queue.poll();              int r = tmp / column, c = tmp % column;//拆解位置              if (img[r][c] == oc && !set.contains(tmp)) {//像素值為舊值，並且該點未被計算過                  img[r][c] = nc;//改為新值                  set.add(tmp);                  if (r + 1 < row) if (img[r + 1][c] == oc) queue.add((r + 1) * column + c);                  if (r - 1 >= 0) if (img[r - 1][c] == oc) queue.add((r - 1) * column + c);                  if (c + 1 < column) if (img[r][c + 1] == oc) queue.add(r * column + c + 1);                  if (c - 1 >= 0) if (img[r][c - 1] == oc) queue.add(r * column + c - 1);              }          }      }  }