733. 图像渲染 - 力扣LeetCode733. 图像渲染 - 有一幅以 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的二维整数数组表示的图画imageimage[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 pairint,int PII; int dx[4]{0,0,1,-1}; int dy[4]{1,-1,0,0}; vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { int previmage[sr][sc]; if(prevcolor) return image; queuePIIq; q.push({sr,sc}); int mimage.size(),nimage[0].size(); while(q.size()) { auto[a,b]q.front(); q.pop(); image[a][b]color; for(int i0;i4;i) { int xadx[i]; int ybdy[i]; if(x0xmy0ynimage[x][y]prev) { q.push({x,y}); } } } return image; } };
