733. 图像渲染 - 力扣（LeetCode）733. 图像渲染 - 有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。为了完成 上色工作： 1. 从初始像素开始，将其颜色改为 color。 2. 对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。 3. 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。 4. 当 没有 其它原始颜色的相邻像素时 停止 操作。最后返回经过上色渲染 修改 后的图像 。 示例 1:[https://assets.leetcode.com/uploads/2021/06/01/flood1-grid.jpg]输入：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]]解释：在图像的正中间，坐标 (sr,sc)=(1,1) （即红色像素）,在路径上所有符合条件的像素点的颜色都被更改成相同的新颜色（即蓝色像素）。注意，右下角的像素 没有 更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。 示例 2:输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0输出：[[0,0,0],[0,0,0]]解释：初始像素已经用 0 着色，这与目标颜色相同。因此，不会对图像进行任何更改。 提示: * m == image.length * n == image[i].length * 1 <= m, n <= 50 * 0 <= image[i][j], color < 216 * 0 <= sr < m * 0 <= sc < nhttps://leetcode.cn/problems/flood-fill/
题目描述
有一幅以m x n的二维整数数组表示的图画image，image[i][j]代表像素值。给你起点坐标sr, sc以及目标颜色color，从起点开始做上色填充：
- 修改起点像素为目标颜色；
- 向上下左右 4 个方向扩散，只处理和起点原始颜色相同的连通像素；
- 不断重复扩散，直到没有符合条件的相邻像素，返回修改后的图像。
示例 输入：
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]]
解题思路
本题属于经典网格连通类题目，可以用BFS 广度优先搜索解决。
- 特判边界：如果起点原始颜色已经等于目标颜色，直接返回原图，避免无效循环；
- 使用队列存储待处理的坐标点；
- 每次从队列取出坐标，修改像素颜色；遍历 4 个方向；
- 坐标不越界，并且像素等于原始旧颜色，则将该点入队等待后续处理；
class Solution { public: typedef pair<int,int> PII; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int prev=image[sr][sc]; if(prev==color) return image; queue<PII>q; q.push({sr,sc}); int m=image.size(),n=image[0].size(); while(q.size()) { auto[a,b]=q.front(); q.pop(); image[a][b]=color; for(int i=0;i<4;i++) { int x=a+dx[i]; int y=b+dy[i]; if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev) { q.push({x,y}); } } } return image; } };
