遞歸遍歷數組問題

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

此方法給出訂貨號對象的2維陣列，靶訂貨號和陣列內的起始位置。它遞歸地遍歷數組 ，計算Ident佔用的連續區域的大小。它還將輸入的Ident項目放在該區域的中間。

通過經由圖陣列循環，並呼籲任何非零元素的探索方法我可以構建在其區域爲中心訂貨號項的數組，並用尺寸相對於它們的區域。

可以看出，用什麼，但小地圖，堆棧溢出。

任何人有完成相同的任務的替代方法是什麼？或者一些見解來幫助我找到一個？

Answer 1

這讓我回到80年代中期。任何洪水填充算法將要求一定的狀態量。不幸的是我不記得算法。對於一個大片來說，有效率可能不會對迷宮有效。

爲了避免遞歸，而不是遞歸，只需添加你會叫一個堆棧的數據。循環四處彈出堆棧頂部的下一個未探索座標。使用堆棧而不是先進先出隊列改善了局部性，儘管它可能不會在這裏產生巨大的影響。

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

在最好的傳統的stackoverflow這沒有看到一個編譯器。 （它也保留了很多原始算法。）

Answer 2

爲了消除遞歸，使座標列表探索和循環，而它包含任何項目;在你的循環中，建立一個新的座標列表來探索，並在循環結束時用新列表替換舊列表。