为什么会出现这种洪水填充算法导致堆栈溢出？

Question

void FloodFill(int layer, int x, int y, int target, int replacement)
{
    if (x < 0) return;
    if (y < 0) return;
    if (x >= _mapWidth) return;
    if (y >= _mapHeight) return;

    if (_mapLayers[layer, x, y] != target) return;

    _mapLayers[layer, x, y] = replacement;

    FloodFill(layer, x - 1, y, target, replacement);
    FloodFill(layer, x + 1, y, target, replacement);
    FloodFill(layer, x, y - 1, target, replacement);
    FloodFill(layer, x, y + 1, target, replacement);

    return;
}

这是到目前为止我的代码，但是当它到达它导致堆栈溢出地图的结束，没有任何人知道如何解决这个问题（可能是一个棘手的状况）？

Answer 1

注意这个呼叫路径存在：

(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...

这是一个无限递归，所以你堆栈溢出。您的支票无法处理此。你必须执行一个额外的检查：

if (_mapLayers[layer, x, y] == replacement) return;

---

即使你已包括上述额外的检查，请注意，最大递归深度是(_mapWidth * _mapHeight)，其可以是非常深的，即使是小的位图（例如，100×100）。

Answer 2

首先，你应该确保target!=replacement（可一次“FloodFill”的inital调用之前完成）。然后，你可能算法中工作，只要_mapWidth和_mapHeight不平凡的大（这在很大程度上取决于你的_mapLayers阵列的内容）。如果这是一个问题，你应该尝试一个非递归算法。创建

class Point
{ 
    public int x, y;
    public Point(int newX, int newY)
    {
         x=newX;
         y=newY;
    }
}

和

 List<Point> pointList;

把初始点进入这个名单，并运行一些类型的循环，直到pointList是空的：取一个点淘汰之列，过程中它像上面并代替原有的递归调用上面放四个邻国再次进入名单。

编辑：这里是完整的例子，没有测试，虽然：

    void FloodFill2(int layer, int xStart, int yStart, int target, int replacement)
    {
        if(target==replacement)
            return;
        List<Point> pointList = new List<Point>();

        pointList.Add(new Point(xStart,yStart));
        while(pointList.Count>0)
        {
            Point p = pointList[pointList.Count-1];
            pointList.RemoveAt(pointList.Count-1);
            if (p.x < 0) continue;
            if (p.y < 0) continue;
            if (p.x >= _mapWidth) continue;
            if (p.y >= _mapHeight) continue;
            if (_mapLayers[layer, p.x, p.y] != target) continue;
            _mapLayers[layer, p.x, p.y] = replacement;

            pointList.Add(new Point(p.x - 1, p.y));
            pointList.Add(new Point(p.x + 1, p.y));
            pointList.Add(new Point(p.x, p.y - 1));
            pointList.Add(new Point(p.x, p.y + 1));
        }
    }

EDIT2：事实上，这里是优化程序的建议：避免插入到列表中，如果插入变得无意义，所以：

            if(p.x>=0) 
                 pointList.Add(new Point(p.x - 1, p.y));
            if(p.x<_mapWidth-1) 
                 pointList.Add(new Point(p.x + 1, p.y));
            if(p.y>=0) 
                 pointList.Add(new Point(p.x, p.y - 1));
            if(p.y<_mapHeight-1) 
                 pointList.Add(new Point(p.x, p.y + 1));