Problèmes de traversée de tableaux récursifs

Question

Je rencontre des problèmes de stackoverflow et j'espère que quelqu'un pourra me donner un aperçu d'une solution non-moins récursive.

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

Cette méthode reçoit un tableau bidimensionnel d'objets Ident, une identité cible et une position de départ dans le tableau. Il parcourt récursivement le tableau en comptant la taille d'une zone continue occupée par l'Ident. Il centre également l'élément Ident entré au milieu de la zone. En faisant une boucle sur la matrice de cartes et en appelant la méthode explorer sur des éléments non nuls, je peux construire un tableau d'éléments Ident centrés dans leurs zones, et avec des tailles relatives à leurs zones.

On peut voir qu'avec n'importe quoi mais de petites cartes, la pile débordera.

Quelqu'un at-il une autre méthode pour accomplir la même tâche? Ou un aperçu pour m'aider à en trouver un?

Answer 1

Cela me ramène au milieu des années 80. Tout algorithme de remplissage d'inondation va nécessiter une certaine quantité d'état. Je ne me souviens malheureusement pas des algorithmes. Ce qui est efficace pour une grande étendue ne sera probablement pas efficace pour un labyrinthe.

Pour éviter la récursivité, au lieu de récurer, ajoutez simplement les données que vous auriez appelées à une pile. Boucle autour de la prochaine coordonnée inexplorée du sommet de la pile. L'utilisation d'une pile plutôt que d'une file d'attente FIFO améliore un peu la localité, même si cela ne va probablement pas faire une énorme différence ici.

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

Dans les meilleures traditions de stackoverflow cela n'a pas vu de compilateur. (Il conserve également une grande partie de l'algorithme d'origine.)

Answer 2

Pour éliminer la récursivité, dressez une liste de coordonnées à explorer et à boucler alors qu'il contient des éléments; Dans votre boucle, créez une nouvelle liste de coordonnées à explorer et, à la fin de la boucle, remplacez l'ancienne par la nouvelle liste.