Problème avec les chemins terminés dans l'algorithme récursif simple

Question

Tout d'abord: ce n'est pas un devoir, c'est pour un projet de passe-temps.

Contexte: Pour mon jeu de puzzle Java-je utiliser un algorithme récursif très simple pour vérifier si certains espaces sur la « carte » sont devenus isolés après est placé un morceau. Isolé dans ce cas signifie: où aucune pièce peuvent être placés dans

algorithme actuel.

public int isolatedSpace(Tile currentTile, int currentSpace){ 
     if(currentTile != null){ 
      if(currentTile.isOpen()){ 
       currentTile.flag(); // mark as visited 
       currentSpace += 1; 
       currentSpace = isolatedSpace(currentTile.rightNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.underNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.leftNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.upperNeighbor(),currentSpace); 
       if(currentSpace < 3){currentTile.markAsIsolated();} // <-- the problem 
      } 
     } 
     return currentSpace; 
    } 

Ce morceau de code renvoie la taille de l'espace vide où la tuile de départ est partie. Cette partie du code fonctionne comme prévu. Mais je suis tombé sur un problème en ce qui concerne le marquage des carreaux et qui est ce qui fait le titre de cette question pertinente;)

Le problème: Le problème est que certaines tuiles ne sont jamais « revisité » (ils renvoient un valeur et se termine, donc ne jamais obtenir une valeur de retour eux-mêmes d'une incarnation ultérieure pour mettre à jour la taille de l'espace vide). Ces tuiles 'oubliées' peuvent faire partie d'un grand espace mais sont marquées comme isolées car elles ont été visitées au début du processus quand currentSpace avait une valeur faible.

Question: Comment améliorer ce code afin de définir la valeur correcte pour les tuiles sans trop de frais généraux? Je peux penser à des solutions laides comme revisiter toutes les tuiles signalées et si elles ont la bonne valeur vérifier si les voisins ont la même valeur, sinon mettre à jour etc. Mais je suis sûr qu'il y a des gens brillants ici sur Stack Overflow avec de bien meilleures idées;)

---

Mise à jour: J'ai apporté quelques modifications.

public int isolatedSpace(Tile currentTile, int currentSpace, LinkedList<Tile> visitedTiles){ 
     if(currentTile != null){ 
      if(currentTile.isOpen()){ 
       // do the same as before 
       visitedTiles.add(); 
      } 
     } 
     return currentSpace; 
    } 

Et la fonction marktiles (uniquement appelée lorsque la spacesize retournée est inférieure à une valeur donnée)

marktiles(visitedTiles){ 
     for(Tile t : visitedTiles){ 
      t.markAsIsolated(); 
     } 
} 

Cette approche est conforme à la réponse de Rex Kerr, au moins si je compris son idée.

Answer 1

Vous devez suivre un processus en deux étapes: recueillir des informations sur l'isolement d'un espace, puis le marquer séparément. Donc, vous devrez d'abord compter tous les espaces (en utilisant une fonction récursive) et ensuite marquer tous les espaces connectés si le critère passe (en utilisant une fonction récursive différente).

Answer 2

Ceci n'est pas une solution générale, mais vous marquez uniquement les espaces comme isolés s'ils se produisent dans une région de deux espaces ou moins. Ne pouvez-vous pas simplifier ce test à «un espace est isolé si (a) il n'a pas de voisins ouverts ou (b) précisément un voisin ouvert et que ce voisin n'a pas d'autres voisins ouverts».