# LeetCode 733： 图像渲染 flood-fill

### 题目：

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

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.

输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2

• imageimage[0] 的长度在范围 [1, 50] 内。
• 给出的初始点将满足 0 <= sr < image.length0 <= 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（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(),避免添加重复点
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;//改为新值
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);
}
}
}
}

+ 订阅