733. 图像渲染
题目描述
输入 m x n 整数矩阵 image 表示一张图片，image[i][j] 是像素颜色。另给出整数 sr、sc 和 color，下标从 0 开始。
记起点像素 image[sr][sc] 原来的颜色为 c。从起点出发，沿上下左右四个方向走，只能经过颜色为 c 的像素。把所有能走到的像素（含起点）都改成 color。
返回修改后的图片。如果 color 与 c 相同，图片不变。
示例 1
输入：image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 输出：[[2,2,2],[2,2,0],[2,0,1]]
解释：与中心相连的值为 1 的格子都变成 2；右下角的 1 只与中心斜向相邻，保持不变。
示例 2
输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 输出：[[0,0,0],[0,0,0]]
解释：新颜色与原颜色都是 0，图片不变。
数据范围
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], color < 2^160 <= sr < m0 <= sc < n
解题思路：广度优先搜索
记下起点原来的颜色 old。如果 old 已经等于 color，直接返回，否则会无限循环。把起点染色后入队，做 BFS：每出队一个像素，检查四个方向的邻居，在界内且颜色为 old 的邻居立刻染成 color 并入队。
为什么正确
队列中的像素都已染成 color；已染色的像素不再等于 old，所以不会重复入队。
复杂度分析
时间 O(mn)，每个像素最多入队一次；空间 O(mn)，用于队列。
易错点
当 old == color 时必须直接返回：染色后像素仍等于 old，会被反复入队，导致死循环。另外要在入队时染色，而不是出队时，否则同一像素可能多次入队。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old == color:
return image
m, n = len(image), len(image[0])
image[sr][sc] = color
queue = collections.deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old:
image[nr][nc] = color
queue.append((nr, nc))
return imageclass Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old == color) {
return image;
}
int m = image.length, n = image[0].length;
image[sr][sc] = color;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sr, sc});
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old) {
image[nr][nc] = color;
q.offer(new int[]{nr, nc});
}
}
}
return image;
}
}class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old == color) {
return image;
}
int m = image.size(), n = image[0].size();
image[sr][sc] = color;
queue<pair<int, int>> q;
q.push({sr, sc});
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old) {
image[nr][nc] = color;
q.push({nr, nc});
}
}
}
return image;
}
};func floodFill(image [][]int, sr int, sc int, color int) [][]int {
old := image[sr][sc]
if old == color {
return image
}
m, n := len(image), len(image[0])
image[sr][sc] = color
queue := [][2]int{{sr, sc}}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, d := range dirs {
nr, nc := cur[0]+d[0], cur[1]+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old {
image[nr][nc] = color
queue = append(queue, [2]int{nr, nc})
}
}
}
return image
}var floodFill = function(image, sr, sc, color) {
const old = image[sr][sc];
if (old === color) {
return image;
}
const m = image.length, n = image[0].length;
image[sr][sc] = color;
const queue = [[sr, sc]];
let head = 0;
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] === old) {
image[nr][nc] = color;
queue.push([nr, nc]);
}
}
}
return image;
};function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
const old = image[sr][sc];
if (old === color) {
return image;
}
const m = image.length, n = image[0].length;
image[sr][sc] = color;
const queue: number[][] = [[sr, sc]];
let head = 0;
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] === old) {
image[nr][nc] = color;
queue.push([nr, nc]);
}
}
}
return image;
}其他解法
两种搜索都把每个像素处理一次，复杂度相同；广度优先用队列没有栈溢出风险，深度优先递归写法更简洁。
解法 2：深度优先搜索 时间 O(m·n)，空间 O(m·n)
记下起点原色 old，若与新颜色相同直接返回。递归函数先把当前像素染成新颜色，再对四个方向中在网格内且颜色等于 old 的邻居递归。染色本身就是访问标记。
代码比广度优先搜索更短，不需要队列。最坏递归深度可达 m·n，Python 需要调高递归上限。
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old == color:
return image
sys.setrecursionlimit(10000)
m, n = len(image), len(image[0])
def dfs(r, c):
image[r][c] = color
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old:
dfs(nr, nc)
dfs(sr, sc)
return imageclass Solution {
int m, n, oldColor, newColor;
void dfs(int[][] image, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != oldColor) return;
image[r][c] = newColor;
dfs(image, r + 1, c);
dfs(image, r - 1, c);
dfs(image, r, c + 1);
dfs(image, r, c - 1);
}
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
oldColor = image[sr][sc];
if (oldColor == color) return image;
m = image.length;
n = image[0].length;
newColor = color;
dfs(image, sr, sc);
return image;
}
}class Solution {
public:
int m, n, oldColor, newColor;
void dfs(vector<vector<int>>& image, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != oldColor) return;
image[r][c] = newColor;
dfs(image, r + 1, c);
dfs(image, r - 1, c);
dfs(image, r, c + 1);
dfs(image, r, c - 1);
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
oldColor = image[sr][sc];
if (oldColor == color) return image;
m = image.size();
n = image[0].size();
newColor = color;
dfs(image, sr, sc);
return image;
}
};func floodFill(image [][]int, sr int, sc int, color int) [][]int {
old := image[sr][sc]
if old == color {
return image
}
m, n := len(image), len(image[0])
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= m || c < 0 || c >= n || image[r][c] != old {
return
}
image[r][c] = color
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
dfs(sr, sc)
return image
}var floodFill = function(image, sr, sc, color) {
const old = image[sr][sc];
if (old === color) return image;
const m = image.length, n = image[0].length;
const dfs = (r, c) => {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] !== old) return;
image[r][c] = color;
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
dfs(sr, sc);
return image;
};function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
const old = image[sr][sc];
if (old === color) return image;
const m = image.length, n = image[0].length;
const dfs = (r: number, c: number): void => {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] !== old) return;
image[r][c] = color;
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
dfs(sr, sc);
return image;
}