使用 dfs 算法时出现运行时错误

Question

我在使用 dfs 解决问题时遇到运行时错误。

这里是错误：

AddressSanitizer：地址 0x7ffce7e6eff8 上的堆栈溢出（pc 0x000000359715 bp 0x7ffce7e6f040 sp 0x7ffce7e6f000 T0

这里是问题link：

(https://leetcode.com/problems/flood-fill/)

这是我的代码：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {

        int color=image[sr][sc];
        dfs(image,sr,sc,color,newColor);
        return image;
    }

    void dfs(vector<vector<int>> &image,int sr,int sc,int color,int newcolor)
    {
         if(sr<0 || sr>=image.size() || sc<0 || sc>=image[0].size() || image[sr][sc]!=color)
        {
            return;
        }

            image[sr][sc]=newcolor;
            dfs(image,sr,sc+1,color,newcolor);
            dfs(image,sr,sc-1,color,newcolor);
            dfs(image,sr+1,sc,color,newcolor);
            dfs(image,sr-1,sc,color,newcolor);

    }


};

它在以下测试用例上失败了：

[[0,0,0],[0,1,1]] 1个 1个 1

我想不通哪里出错了。

谢谢。

Answer 1

检查 newColor != color，否则你会无限递归，因为你依赖颜色变化来避免重新访问以前访问过的像素。

这正是您失败的测试用例所发生的情况。