递归遍历数组问题

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

为了消除递归，使坐标列表探索和循环，而它包含任何项目;在你的循环中，建立一个新的坐标列表来探索，并在循环结束时用新列表替换旧列表。