【C++算法】79.BFS解决FloodFill算法_图像渲染

题目链接：

733. 图像渲染

题目描述：

解法

BFS一层层剥开。

C++ 算法代码：

class Solution {// 定义坐标对的类型别名，表示(x,y)坐标typedef pair<int, int> PII;// 定义四个方向的偏移量：右、左、下、上int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {// 记录初始位置的颜色int prev = image[sr][sc];// 如果初始颜色和目标颜色相同，直接返回原图if (prev == color)return image;// 获取图像的行数和列数int m = image.size(), n = image[0].size();// 创建队列用于BFSqueue<PII> q;// 将起始位置加入队列q.push({sr, sc});// 开始BFSwhile (!q.empty()) {// 取出队首元素auto [a, b] = q.front();// 将当前位置的颜色改为目标颜色image[a][b] = color;q.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {// 计算新坐标int x = a + dx[i], y = b + dy[i];// 检查新坐标是否在图像范围内，并且颜色与初始颜色相同if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {// 将新坐标加入队列q.push({x, y});}}}// 返回处理后的图像return image;}
};