2 
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;
}

これはこれまでの私のコードですが、マップの最後に到達するとスタック オーバーフローが発生します。問題を解決する方法を知っている人はいますか (おそらくトリッキーな状態です)。

4

2 に答える 2

3

次の呼び出しパスが存在することに注意してください。

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

これは無限再帰であるため、スタック オーバーフローが発生します。あなたの小切手はこれに対処できません。追加のチェックを 1 つ実行する必要があります。

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

上記の追加のチェックを含めた場合でも、再帰の最大深度は(_mapWidth * _mapHeight)であることに注意してください。これは、小さなビットマップ (100 x 100 など) の場合でも非常に深くなる可能性があります。

于 2010-01-17T14:34:31.330 に答える
2

まず、target!=replacement('FloodFill' の最初の呼び出しの前に 1 回実行できます) ことを確認する必要があります。次に、_mapWidth と _mapHeight が異常に大きくない限り (_mapLayers 配列の内容に大きく依存します)、アルゴリズムが機能する可能性があります。これが問題になる場合は、非再帰アルゴリズムを試してください。作成する

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

そして

 List<Point> pointList;

最初の点をこのリストに入れ、pointList が空になるまで何らかのループを実行します。リストから 1 つの点を取り出し、上記のように処理し、上記の元の再帰呼び出しの代わりに、4 つの隣接点を再びリストに入れます。

編集:ここに完全な例がありますが、テストはしていません:

    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));
于 2010-01-17T14:52:56.027 に答える