Comment je trouve chemin à l'aide labyrinthe de tableau 2D en Java

Question

B B B B B 

B B B O B 

B B S O B 

B O O B B 

B B X B B 

Ici,

S = Point de départ (2,2)

B = Bloc

O = Ouvrir

X = Sortie

Je veux faire un labyrinthe qui va vérifier nord, ouest, est et sud. Si X est autour, il retournera le programme. Si ce n'est pas le cas, vérifiez si un 'O' est autour du point de départ et passez le nouveau point de départ de manière récursive. Il n'y a aucun moyen d'y aller et 'X' n'est pas trouvé il retournera au point de départ original (2,2) et vérifiera l'ouest, l'est et le sud.

après le programme, je me suis:

B B B B B 

B B B + B 

B B + + B 

B O + B B 

B B X B B 

mais je me attends à la sortie après la récursion est:

B B B B B 

B B B - B 

B B + - B 

B O + B B 

B B X B B 

C'est mon code en ce moment:

public static void Find_Path(char[][] maze, int startX, int startY){ 
int x[] = { -1, 0, 0, 1}; 
int y[] = {0,-1,1,0}; 
boolean found = false; 
maze[startX][startY] = '+'; 
for(int i = 0; i < 4 ; i++){// check if there are 'X' around the S. 
    int afterX = x[i] + startX; 
    int afterY = y[i] + startY; 
    if(maze[afterX][afterY] == 'X'){// if yesy, return. 
    found = true; 
    return; 
    } 
} 

for(int i = 0; i < 4 ; i++){// if no, check for 'O' 
    int afterX = x[i] + startX; 
    int afterY = y[i] + startY; 
    if(maze[afterX][afterY] == 'O'){ 
    Find_Path(maze, afterX, afterY); 
    if(!found){ 
    maze[afterX][afterY] = '-'; 
    } 
} 
} 

startX et startY sont l'index du point de départ.

Je ne sais pas comment faire tourner le mauvais chemin '-'. Le programme vérifiera d'abord le nord Si le sommet est B, il fera marche arrière et retournera au point de départ. Ensuite, il ira vers l'est, l'ouest et le sud.

Quelqu'un peut-il m'aider? THX! @Muntasir

BBBBB 
BBOOB 
XOBOB 
BSOBB 
BBBBB 

BBBBB 
BBOOB 
X+BOB (It should stop right here, because there is X around it.) 
BSOBB 
BBBBB 

BBBBB 
BBOOB 
X+BOB (but, somehow it go to the right of the startpoint and mark the 'O' to '+' 
BS+BB 
BBBBB 

Answer 1

utiliser une variable globale (un drapeau) pour déterminer si vous avez trouvé le bon chemin.

Par exemple:

public class YourClass{ 
    static boolean found = false; // the global flag 
    // your existing code 

    public static void Find_Path(char[][] maze, int startX, int startY){ 
     // .... 
     for(int i = 0; i < 4 ; i++){ 
      // ... 
      if(maze[afterX][afterY] == 'X'){ 
       found = true; // path found 
       return; 
      } 
     } 
     for(int i = 0; i < 4 ; i++){ 
      // ... 
      if(found) // path already found in earlier recursive call; no need to search anymore 
       return; 
      else{ // path not found yet, have to continue searching 
       if(maze[afterX][afterY] == 'O'){ 
        Find_Path(maze, afterX, afterY); 
        if(!found){ // path not found 
         maze[afterX][afterY] = '-'; 
        } 
       } 
      } 
     } 
    } 
} 

Answer 2

Les algorithmes que vous recherchez sont appelés en largeur et profondeur de recherche-première recherche. Un problème que vous rencontrerez est s'il existe un cycle dans votre labyrinthe. Par exemple, que se passe-t-il si vous avez ceci? Ensuite, l'algorithme peut rester coincé dans une boucle que vous ne pouvez pas échapper.

La méthode classique pour résoudre ce problème consiste à "colorer" les sommets en utilisant une autre structure de données représentant si les sommets ont déjà été visités ou non.

Cette conférence MIT OCW peut aider à vous orienter dans la bonne direction: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-13-breadth-first-search-bfs/

Pour répondre à votre question directement, mais, pensez à des cas de base. Qu'est-ce qui empêche les boucles de tourner et de tourner lorsque vous trouvez le X? Dans l'état actuel, il semble que la seule chose qui arrête l'itération/récursion est que vous manquiez d'endroits pour regarder. Vous aurez besoin d'une sorte de variable pour indiquer à la seconde que la boucle doit cesser de chercher.

Answer 3

Comme la question se pose cette solution devrait fonctionner:

import java.util.Arrays; 

public class TwoDSolver { 

private char[][] maze; 
private String currPath; 
private int currX; 
private int currY; 
private boolean unsolvable; 

public static void main(String[] args) { 
    char[][] customMaze = { 
      {'B', 'B', 'B', 'B', 'B'}, 
      {'B', 'B', 'B', 'O', 'B'}, 
      {'B', 'B', 'S', 'O', 'B'}, 
      {'B', 'O', 'O', 'B', 'B'}, 
      {'B', 'B', 'X', 'B', 'B'} 
    }; 

    String startPath = ""; 
    int startX = 2; 
    int startY = 2; 
    TwoDSolver solver = new TwoDSolver(customMaze, startX, startY, startPath, false); 
    // place a plus at the start point 
    solver.placePlus(); 
    solver.solveMaze(); 
    if (solver.unsolvable) { 
     System.out.println("The maze is unsolvable"); 
    } else { 
     System.out.println("Solved, A correct path is: " + solver.currPath); 
    } 
    solver.printMaze(); 


} 

// constructor 
TwoDSolver(char[][]aMaze, int stX, int stY, String currentPath, boolean noSolution) { 
    maze = aMaze; 
    currX = stX; 
    currY = stY; 
    currPath = currentPath; 
    unsolvable = noSolution; 
} 

// indicate taken path 
void placePlus() { 
    maze[currX][currY] = '+'; 
} 

// for backtracking 
void placeMinus() { 
    maze[currX][currY] = '-'; 
} 

// solve 
// priority in this order East, West, South, North 
void solveMaze() { 
    // check for a win 
    if (checkForWin()) { 
     return; 
    } 
    // No win, so let's check for an opening 
    // check east 
    if (currY + 1 < maze[currX].length && checkForOpen(currX, currY + 1)) { 
     currY++; 
     placePlus(); 
     currPath += "E"; // Append East to our current path 
     // recursive call continue searching 
     solveMaze(); 
     // check west 
    } else if (currY - 1 >= 0 && checkForOpen(currX, currY - 1)) { 
     currY--; 
     placePlus(); 
     currPath += "W"; 
     solveMaze(); 
     // check south 
    } else if (currX + 1 < maze.length && checkForOpen(currX + 1, currY)) { 
     currX++; 
     placePlus(); 
     currPath += "S"; 
     solveMaze(); 
     // check north 
    } else if (currX - 1 >= 0 && checkForOpen(currX - 1, currY)) { 
     currX--; 
     placePlus(); 
     currPath += "N"; 
     solveMaze(); 
    } else { // we've hit a dead end, we need to backtrack 
     if (currPath.length() == 0) { 
      // we're back at the starting point, the maze is unsolvable 
      unsolvable = true; 
      return; 
     } else { 
      // we've reached a dead end, lets backtrack 
      placeMinus(); 
      backTrack(); 
     } 
    } 
} 

// see if the spot at a give x, y is open 
boolean checkForOpen(int x, int y) { 
    return maze[x][y] == 'O'; 
} 

// see if any of the surrounding spots are the exit 
boolean checkForWin() { 
    // make sure to protect against out of bounds as well 
    return ((currY + 1 < maze[currX].length && maze[currX][currY + 1] == 'X') || 
      (currY - 1 >= 0 && maze[currX][currY - 1] == 'X') || 
      (currX + 1 < maze[currX].length && maze[currX + 1][currY] == 'X') || 
      (currX -1 >= 0 && maze[currX -1][currY] == 'X')); 
} 

void backTrack() { 
    // sanity chek currPath.length() should always be > 0 when we call backTrack 
    if (currPath.length() > 0) { 
     placeMinus(); 
     switch (currPath.charAt(currPath.length() - 1)) { 
     case 'E': 
      currY--; 
      break; 
     case 'W': 
      currY++; 
      break; 
     case 'S': 
      currX--; 
      break; 
     case 'N': 
      currX++; 
      break; 
     } 
     currPath = currPath.substring(0, currPath.length()-1); 
     solveMaze();  
    } 
} 

void printMaze() { 
    for (int i = 0; i < maze.length; i++) { 
     System.out.println(Arrays.toString(maze[i])); 
    } 
} 

} 

Pour votre exemple Mazé la sortie est:

Solved, A correct path is: S 
[B, B, B, B, B] 
[B, B, B, -, B] 
[B, B, +, -, B] 
[B, O, +, B, B] 
[B, B, X, B, B] 

Pour le labyrinthe exemple purposed par @William John Howard qui n'a pas de solution :

{'B', 'B', 'B', 'B', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'O', 'S', 'O', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'B', 'B', 'B', 'B'} 

la sortie est:

The maze is unsolvable 
[B, B, B, B, B] 
[B, -, -, -, B] 
[B, -, +, -, B] 
[B, -, -, -, B] 
[B, B, B, B, B] 

Une chose à noter à propos de cette solution et cette façon d'aborder le problème: Cela ne fournira pas le plus court chemin vers la sortie

Cette solution donne la priorité dans cet ordre: Est, Ouest , Nord sud.

Voici un exemple de ce que je veux dire:

labyrinthe de départ:

{'B', 'B', 'B', 'X', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'O', 'S', 'O', 'B'}, 
{'B', 'O', 'O', 'O', 'B'}, 
{'B', 'B', 'B', 'B', 'B'} 

Sortie:

Solved, A correct path is: ESWWNNEE 
[B, B, B, X, B] 
[B, +, +, +, B] 
[B, +, +, +, B] 
[B, +, +, +, B] 
[B, B, B, B, B] 

Comme vous pouvez le voir, il y a plusieurs chemins corrects à la sortie, NE, EN, WNEE, SENN, SWNNEE, ESWWNNEE (celui que cet algo a choisi en raison de la priorité de direction).

Je pense que la principale chose que vous manquez du code affiché est un moyen de garder une trace de votre chemin en cours et faire marche arrière quand vous frappez une impasse.