图像渲染 图解题解

这道题到底在问什么

输入

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, 1)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。（动画第 7 步）

最优解：一步一步想明白

1. 3记住「记原色 → 栈里弹一个、染四周同色的、再入栈」,下面逐帧套它。
2. 4先看起点 (1, 1)(紫色),它的原色 old = 1。我们要把和它连通的同色格子都染成 2。
3. 5判一下:新色 2 和原色 1 不一样,不会出现「越染越像原色」的死循环,可以放心开染。要是两者相等,这一步就该直接返回了。
4. 6先把起点 (1, 1) 染成 2(变绿),压进栈。接下来不断从栈里弹格子、向四周扩散。
5. 7从栈顶弹出 (1, 1)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
6. 8往上看邻居 (0, 1):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
7. 9把 (0, 1) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
8. 10往左看邻居 (1, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
9. 11把 (1, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
10. 12从栈顶弹出 (1, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
11. 13往下看邻居 (2, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
12. 14把 (2, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
13. 15往上看邻居 (0, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
14. 16把 (0, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
15. 17从栈顶弹出 (0, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
16. 18从栈顶弹出 (2, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
17. 19从栈顶弹出 (0, 1)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
18. 20往右看邻居 (0, 2):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
19. 21把 (0, 2) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
20. 22从栈顶弹出 (0, 2)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
21. 23栈空了,扩散结束。这一片四连通的 1 全被染成了 2(绿色),一共 6 个格子;右下角那个 1 被 0 隔开、够不着,保持不变。最终网格就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
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])
        stack = [(sr, sc)]
        image[sr][sc] = color
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old:
                    image[nr][nc] = color
                    stack.append((nr, nc))
        return image

#include <vector>
using namespace std;
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();
        vector<pair<int,int>> st{{sr, sc}};
        image[sr][sc] = color;
        int dirs[5] = {1,0,-1,0,1};
        while (!st.empty()) {
            auto [r, c] = st.back(); st.pop_back();
            for (int d = 0; d < 4; ++d) {
                int nr = r + dirs[d], nc = c + dirs[d+1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old) {
                    image[nr][nc] = color;
                    st.push_back({nr, nc});
                }
            }
        }
        return image;
    }
};

import java.util.*;
class 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;
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[]{sr, sc});
        image[sr][sc] = color;
        int[] dirs = {1,0,-1,0,1};
        while (!st.isEmpty()) {
            int[] cur = st.pop();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dirs[d], nc = cur[1] + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old) {
                    image[nr][nc] = color;
                    st.push(new int[]{nr, nc});
                }
            }
        }
        return image;
    }
}

复杂度

面试官可能追问