【LeetCode-简单】733. 图像渲染 - DFSBFS

【LeetCode-简单】733. 图像渲染 - DFS/BFS

733. 图像渲染

解法一：BFS
从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。

注意：因为初始位置的颜色会被修改，所以需要保存初始位置的颜色，以便于之后的更新 *** 作。

class Solution {
public:
    const int dx[4]={0,1,0,-1};
    const int dy[4]={1,0,-1,0};
    vector> floodFill(vector>& image, int sr, int sc, int newColor) {
        int curcolor=image[sr][sc];
        if(newColor==curcolor) return image;
        int n=image.size(), m=image[0].size();
        queue> que;
        que.emplace(sr, sc);
        image[sr][sc]=newColor;
        while (!que.empty()) {
            int x = que.front().first, y = que.front().second;
            que.pop();
            for (int i=0;i<4;i++) {
                int mx=x+dx[i], my=y+dy[i];
                if (mx>=0 && mx=0 && my 
C++ pair的基本用法总结
 
 
 
emplace *** 作是C++11新特性，新引入的的三个成员emplace_front、emplace 和 emplace_back。这些 *** 作构造而不是拷贝元素到容器中，这些 *** 作分别对应push_front、insert和push_back，允许我们将元素放在容器头部、一个指定的位置和容器尾部。
 
 
 
 
两者的区别：当调用insert时，是将对象传递给insert，对象被拷贝到容器中，而当我们使用emplace时，是将参数传递给构造函，emplace使用这些参数在容器管理的内存空间中直接构造元素。
 
 
解法二：DFS
 从给定的起点开始，进行深度优先搜索。每搜索到一个方格，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。
 
同样，由于初始位置的颜色会被修改，所以需要保存初始位置的颜色，以便于之后的更新 *** 作。
 
class Solution {
public:
    vector> floodFill(vector>& image, int sr, int sc, int newColor) {
        int color=image[sr][sc];
	    if (color==newColor) return image;
	    if (sr>=0 && sr=0 && sc 
力扣给出的题解代码如下：
 
class Solution {
public:
    const int dx[4] = {1, 0, 0, -1};
    const int dy[4] = {0, 1, -1, 0};
    vector> floodFill(vector>& image, int sr, int sc, int newColor) {
        int curcolor = image[sr][sc];
        if (curcolor != newColor) {
            dfs(image, sr, sc, curcolor, newColor);
        }
        return image;
    }
    void dfs(vector>& image, int x, int y, int color, int newColor) {
        if (image[x][y] == color) {
            image[x][y] = newColor;
            for (int i = 0; i < 4; i++) {
                int mx=x+dx[i], my=y+dy[i];
                if (mx>=0 && mx=0 && my
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5636447.html