/*有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标?(sr, sc)?表示图像渲染开始的像素值（行 ，列）和一个新的颜色值?newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/flood-fill 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
//输入: //image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]] //sr = 1, sc = 1, newColor = 2 //输出 : [[2, 2, 2], [2, 2, 0], [2, 0, 1]] // 解析 : // 在图像的正中间，(坐标(sr, sc) = (1, 1)), // 在路径上所有符合条件的像素点的颜色都被更改成2。 // 注意，右下角的像素没有更改为2， // 因为它不是在上下左右四个方向上与初始点相连的像素点。 // // 来源：力扣（LeetCode） // 链接：https 😕/leetcode-cn.com/problems/flood-fill //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/* 给一个地图向周围搜索的这类题型基本都可以用DFS 向上下左右四个方向搜索 */ class Solution { public: void Dfs(vector<vector<int>>& image, vector<vector<int>>& books, int sr, int sc, int oldcolor, int newcolor, int row, int col) { //渲染当前结点 image[sr][sc] = newcolor; books[sr][sc] = 1; //上下左右，深度遍历 for (int i = 0; i < 4; ++i) { //不能直接用sr，sc渲染,sr，sc还有其他三个方向需要渲染 int newsr = sr; int newsc = sc; if (i == 0) { //上 newsr -= 1; } else if (i == 1) { //下 newsr += 1; } else if (i == 2) { //左 newsc -= 1; } else { //右 newsc += 1; } //如果越界则continue if (newsr >= row || newsr < 0 || newsc >= col || newsc < 0) continue; //如果未被修改过且颜色等于oldcolor，则进行渲染 if (image[newsr][newsc] == oldcolor && books[newsr][newsc] == 0) Dfs(image, books, newsr, newsc, oldcolor, newcolor, row, col); } } vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { if (image.empty()) return image; int row = image.size(); int col = image[0].size(); vector<vector<int>> books; books.resize(row); for (int i = 0; i < row; ++i) { books[i].resize(col, 0); } int oldcolor = image[sr][sc]; Dfs(image, books, sr, sc, oldcolor, newColor, row, col); return image; } };