图像渲染

怎样从“image 是二维图片网格，从点击位置 sr、sc 出发，只把和起点原颜色相同且四方向连通的区域填成 newColor；不是所有同色格子都会被改。”推导出 网格 DFS · 填色，并证明每次状态变化都不会漏掉答案？

中心结论：把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。最后返回经过上色渲染后的图像。

image 和 image[0] 的长度在范围 [1, 50] 内。 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。 image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

在本站主例中，image 是二维图片网格，从点击位置 sr、sc 出发，只把和起点原颜色相同且四方向连通的区域填成 newColor；不是所有同色格子都会被改。

算法最终需要得到或观察：起点所在的同色四方向连通块全变 newColor，不连通的同色格子保持原样。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 oldColor、newColor、当前坐标、当前格子值、判断结果、DFS 调用栈。
3. 3转移每一步按照 把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。
4. 4收尾读取 起点所在的同色四方向连通块全变 newColor，不连通的同色格子保持原样。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：oldColor、newColor、当前坐标、当前格子值、判断结果、DFS 调用栈。

给出一个二维的图片点阵，每个点阵都有一个数字。给出一个起点坐标，要求从这个起点坐标开始，把所有与这个起点连通的点都染色成 newColor。 这一题是标准的 Flood Fill 算法。可以用 DFS 也可以用 BFS 。

把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。

执行过程中持续维护：oldColor、newColor、当前坐标、当前格子值、判断结果、DFS 调用栈。

正确性依赖以下不变量：仅改与起点同色且四方向连通的格子。；后续判断始终使用 oldColor，不用 newColor 判断能否继续扩散。；不是所有同色格子都会被改；右下角同色但不连通时保持不变。

面试时可以压缩为：记录 oldColor := image[sr][sc]，若 oldColor == color 直接返回；否则 DFS 只访问不越界且 image[r][c] == oldColor 的格子，改色后向上下左右递归。时间 O(m*n)，空间 O(m*n) 递归栈。

落到当前题，执行机制可以压缩为：把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入image 是二维图片网格，从点击位置 sr、sc 出发，只把和起点原颜色相同且四方向连通的区域填成 newColor；不是所有同色格子都会被改。 因为：把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。
2. 2从 (1,1) 开始 BFS 填色起点入队。 因为：只改与起点同色的连通区域。
3. 3涂色 (0,1) → 2当前格改色,四邻入队。 因为：BFS 保证整块连通区域被覆盖。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5涂色 (0,2) → 2当前格改色,四邻入队。 因为：BFS 保证整块连通区域被覆盖。
6. 6涂色 (0,0) → 2当前格改色,四邻入队。 因为：BFS 保证整块连通区域被覆盖。
7. 7填色完成队列为空或同色块处理完。 因为：O(mn) BFS。
8. 8收尾与复杂度起点所在的同色四方向连通块全变 newColor，不连通的同色格子保持原样。 因为：时间 O(m*n) · 空间 O(m*n)。把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	color := image[sr][sc]
	if newColor == color {
		return image
	}
	dfs(image, sr, sc, newColor)
	return image
}

func dfs(image [][]int, x, y int, newColor int) {
	if image[x][y] == newColor {
		return
	}
	oldColor := image[x][y]
	image[x][y] = newColor
	for i := 0; i < 4; i++ {
		if (x+dir[i][0] >= 0 && x+dir[i][0] < len(image)) && (y+dir[i][1] >= 0 && y+dir[i][1] < len(image[0])) && image[x+dir[i][0]][y+dir[i][1]] == oldColor {
			dfs(image, x+dir[i][0], y+dir[i][1], newColor)
		}
	}
}

func main() {
    // 1. 主例
    //    输入：mode="flood-fill", grid=[["1","1","1"],["1","1","0"],["1","0","1"]], sr=1, sc=1, color="2"
    //    期望：起点所在的同色四方向连通块全变 newColor，不连通的同色格子保持原样。
    //
    // 2. 失败 / 未命中
    //    检查：把所有同色格子都改掉。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC200 岛屿；LC695 面积
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意image 是二维图片网格，从点击位置 sr、sc 出发，只把和起点原颜色相同且四方向连通的区域填成 newColor；不是所有同色格子都会被改。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化把每个格子看成图节点，上下左右相邻看成边，DFS/BFS 找起点所在的同色连通分量。
4. 4证明仅改与起点同色且四方向连通的格子。；后续判断始终使用 oldColor，不用 newColor 判断能否继续扩散。；不是所有同色格子都会被改；右下角同色但不连通时保持不变。
5. 5复杂度时间 O(m*n)，空间 O(m*n)