再帰的配列トラバーサルの問題

Question

私はいくつかのスタックオーバーフローの問題を抱えています。うまくいけば、誰かが私に非再帰的でない解決法についていくつかの洞察を与えることができます。

Ident[][] map = ... 

private int explore(Ident item, int xcoord, int ycoord) { 
    if ((map[xcoord][ycoord] == null) || !map[xcoord][ycoord].equals(item)) 
      return 0; 

    map[xcoord][ycoord] = null; 
    int sumX, sumY, counter = 1; 
    item.translate(xcoord, ycoord); 

    for (int y = -1; y <= 1; y++) 
     for (int x = -1; x <= 1; x++) { 
      sumX = x + xcoord; 
      sumY = y + ycoord; 
      if (((y != 0) || (x != 0)) && (sumX >= 0) && (sumX < map.length) && 
        (sumY >= 0) && (sumY < map.[0].length)) 
        counter += explore(item, sumX, sumY); 
      } 
     } 
    } 
    return counter; 
} 

このメソッドには、Identオブジェクト、ターゲットIdentおよび配列内の開始位置の2次元配列が与えられます。それは再帰的に配列 を通過し、Identが占める連続領域の大きさを数えます。また、入力されたIdent項目をその中央に配置します。

マップ配列をループし、null以外の要素についてexploreメソッドを呼び出すことで、その領域を中心としたIdentアイテムの配列を構築できます。

小さいマップ以外のものでは、スタックがオーバーフローすることがわかります。

誰も同じタスクを実行する別の方法がありますか？または私が1つを見つけるのを助けるためのいくつかの洞察？

Answer 1

これは80年代半ばにさかのぼります。どのフラッドフィルアルゴリズムも一定量の状態を必要とします。残念ながらアルゴリズムを覚えていません。おそらく、迷路にとって効率的ではないでしょう。

再帰を避けるには、呼び出したデータをスタックに追加するだけです。未知の次の座標をスタックの先頭からポップする周りをループします。 FIFOキューではなくスタックを使用すると、ローカリティが少し向上しますが、ここでは大きな違いはありません。

private int explore(Ident item, int xcoord, int ycoord) { 
    int counter = 0; 

    Queue<Point> stack = Collections.asLifoQueue(new ArrayDeque<Point>()); 
    stack.add(new Point(xcoord, ycoord)); 

    while (!stack.isEmpty()) { 
     Point point = stack.remove(); 
     xcoord = point.x; 
     ycoord = point.y; 

     if (!item.equals(map[xcoord][ycoord])) { 
      continue; 
     } 

     ++counter; 
     map[xcoord][ycoord] = null; 
     item.translate(xcoord, ycoord); 

     for (int y = -1; y <= 1; y++) 
      for (int x = -1; x <= 1; x++) { 
       int sumX = x + xcoord; 
       int sumY = y + ycoord; 
       if (
        !(x == 0 && y == 0) && 
        0 <= sumX && sumX < map.length && 
        0 <= sumY && sumY < map[0].length 
       ) { 
        stack.add(new Point(sumX, sumY)); 
       } 
      } 
     } 
    } 
    return counter; 
} 

これは、コンパイラを見ていない最高の伝統です。 （元のアルゴリズムの多くも保持しています。）

Answer 2

再帰をなくすには、アイテムが含まれている間に探索およびループする座標のリストを作成します。あなたのループで探索する新しい座標リストを作成し、ループの終わりに古いリストを新しいリストに置き換えます。