c++ - Flood Fill递归堆栈溢出

Question

如果我尝试填充一个 100x100 的矩形，则会出现溢出。50x50 效果很好。

有没有办法解决溢出问题？

我还打印出 Stack Number，有时工作矩形 Stack 比大的 Stack 高(它在 7000 左右崩溃)。

void draw(int x, int y)
{
if ((x >= 0 && x < 100) && (y >= 0 && y < 100))
    {
            canvas.set_pixel(x, y);
            if (!canvas.get_pixel(x, y + 1))draw(x, y + 1);
            if (!canvas.get_pixel(x, y-1))draw(x, y - 1);
            if (!canvas.get_pixel(x - 1, y))draw(x - 1, y);
            if (!canvas.get_pixel(x+1, y))draw(x + 1, y);   

    }

    return;
}

Answer 1

堆栈溢出的原因是递归太深了。

它会深入到什么地方？好吧，按照你设计的算法 - 它实际上会深入100*100=10,000 !

让我们看看 Canvas 的填充顺序是什么——假设 Canvas 是空的，我们从中间开始填充:

• 设置中间像素

• 转到 x,y+1

• 这样做，直到到达边缘

• 在边缘 - 移动到 x-1,0(记住，我们在顶部)

• 一直走到底部

等等

关键是——你会越来越深，直到填满 Canvas ，然后在 Canvas 周围有一个递归调用“链”，这是一种浪费:)

Benjamin 是正确的，你可以使用堆栈，但堆栈基本上做完全相同的事情(只是没有递归)，所以堆栈也将达到 10,000 的深度。仍然是一种浪费，在某些情况下你会耗尽内存(对于位图 Canvas ，每个像素占用 1 位，但对于 x,y 堆栈每个像素将有 2 个整数，因此可能比 Canvas 占用多 64 倍的内存)

相反 - 使用队列!几乎相同的代码:

void draw(int x, int y)
{
    struct coordinate { int x, y; };
    std::queue<coordinate> to_draw; // <- changed from stack to queue
    to_draw.push({x, y});

    while (!to_draw.empty())
    {
        auto top = to_draw.front(); // <- changed from top to front
        to_draw.pop();
        if (  (top.x >= 0 && top.x < 100)
           && (top.y >= 0 && top.y < 100)
           && !canvas.get_pixel(top.x, top.y))
        {
            canvas.set_pixel(top.x, top.y);
            to_draw.push({top.x, top.y + 1});
            to_draw.push({top.x, top.y - 1});
            to_draw.push({top.x + 1, top.y});
            to_draw.push({top.x - 1, top.y});
        }            
    }
}

现在需要的内存是<=4*100 !换句话说 - 通过从堆栈更改为队列，我们​​将所需的内存从 N*N 更改为至 4*N .