LeetCode刷题记录：733. 图像渲染

英雄爱吃土豆片

发布于 2020-10-29 11:01:52

5070

发布于 2020-10-29 11:01:52

733. 图像渲染

解题思路： 广度优先遍历（BFS）。首先记录下起点初始的颜色，染色（即将值修改为newColor）后将起点的坐标压入队列。之后进入大循环，大循环内取出队列头部的元素（存储坐标的数对），在小循环中依次检查取出的坐标对应的数组元素的上下左右位置的元素是否和初始颜色相同（使用了两个数组存储了计算上下左右坐标时需要加上的值），若相同，则将其染色并压入队列。若超出数组范围则直接退出小循环，继续大循环。直到最后队列中没有元素，即搜索已经完成，退出大循环，此时已经染色完成。

通关代码：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    	const int bx[] = {0, 0, -1, 1};
    	const int by[] = {1, -1, 0, 0};
    	int ROW = image.size();
    	int COLUMN = image[0].size();
    	
    	
		if (image[sr][sc] == newColor) {
			return image;
		}
		
		int init = image[sr][sc];
		image[sr][sc] = newColor;
		
		queue<pair<int, int>> q;
		q.emplace(pair<int, int>(sr, sc));
		
		int x, y;
		for (; !q.empty();) {
			x = q.front().first;
			y = q.front().second;
			q.pop();
			
			for (int i = 0; i < 4; i++) {
				if (x + bx[i] < ROW && y + by[i] < COLUMN && x + bx[i] >= 0 && y + by[i] >= 0) {
					if (image[x + bx[i]][y + by[i]] == init) {
						image[x + bx[i]][y + by[i]] = newColor;
						q.emplace(pair<int, int>(x + bx[i], y + by[i]));
					}
				}
				
			}
		}
		
		return image;
    }
};

通关截图：