迷宮解決算法Java（遞歸）

Question

我完全停留在本週末的作業分配上。

對於一些愚蠢的原因，當遞歸遍歷器碰到我的迷宮（'E'）末尾時，它並沒有停下來，而是繼續前進。

這裏是讀者：

public class mainProg { 


    public static void main(String[] args) { 
     // The name of the file to open. 

     Scanner reader = new Scanner(System.in); // Reading from System.in 
     System.out.println("Enter the name of textfile to be read (add .txt): "); 
     String fileName = reader.next(); 
     char temp; 
     // This will reference one line at a time 
     String line = null; 
     int count = 1; 
     int heightCounter = 0; 
     try { 
      // FileReader reads text files in the default encoding. 
      FileReader fileReader = 
       new FileReader(fileName); 

      // Always wrap FileReader in BufferedReader. 
      BufferedReader bufferedReader = 
       new BufferedReader(fileReader); 
      int height = 0, width = 0, startx = 0, starty = 0, endx = 0, endy= 0; 
      char [][] maze = null; 
      while((line = bufferedReader.readLine()) != null) { 
       System.out.println(line); 
       switch (count) { 
       case (1): 
        height = Integer.parseInt(line.substring(0, line.indexOf(' '))); 
        width = Integer.parseInt((line.substring(line.indexOf(' ')+1))); 
        maze = new char [height][width]; 
        break; 
       case (2): 
        temp = line.charAt(0); 
        starty = Character.getNumericValue(temp); 
        temp = line.charAt(2); 
        startx = Character.getNumericValue(temp); 
        break; 
       case (3): 
        endy = Integer.parseInt(line.substring(0, line.indexOf(' '))); 
        endx = Integer.parseInt((line.substring(line.indexOf(' ')+1))); 
        break; 
       default: 
        int counter = 0; 
        for (int iterator = 0; iterator < line.length(); iterator++){ 
         if(line.charAt(iterator) != ' '){ 
          maze[heightCounter][counter] = line.charAt(iterator); 
          counter++; 
         } 
        } 
        heightCounter++; 
        break; 
       } 

       count++; 
      } 
      maze[starty][startx] = 'S'; 
      maze[endy][endx] = 'E'; 
      mazeCreator ma = new mazeCreator(maze); 
      ma.start(starty, startx); 
      System.out.println(ma.result); 
      // Always close files. 
      bufferedReader.close();  
      System.out.println("Height: " + height + " Width: " + width); 
      System.out.println("Starty: " + starty + " Startx: " + startx); 
      System.out.println("Endy: " + endy + " Endx: " + endx); 
      System.out.println(ma.result); 
     } 
     catch(FileNotFoundException ex) { 
      System.out.println(
       "Unable to open file '" + 
       fileName + "'");     
     } 
     catch(IOException ex) { 
      System.out.println(
       "Error reading file '" 
       + fileName + "'");     
      // Or we could just do this: 
      // ex.printStackTrace(); 
     } 
    } 

} 

這裏是我的迷宮類：

package com.todai.first.project.testMaze; 

public class mazeCreator { 

     char [][] maze; 
     char PATH = 'x'; 
     char VISITED = 'y'; 
     String result = ""; 
     int starty, startx; 

     public mazeCreator (char[][] maze){ 
      this.maze = maze; 
     } 

     public void start (int starty, int startx) { 
      this.starty = starty; 
      this.startx = startx; 
      traverse(starty, startx); 
     } 
     private boolean isValid (int row, int col){ 
      boolean valid = false; 

      if (row >= 0 && row < maze.length && 
         col >= 0 && col < maze[row].length){ 
       if (maze[row][col] == '0' || maze[row][col] == 'E' || maze[row][col] == PATH) { 
        valid = true; 
       } 
      } 
      return valid; 
     } 
     private boolean traverse (int row, int col) { 
      System.out.println("I'm here: \t" + row +","+ col + "\t :: " + maze[row][col]); 
      if (maze[row][col] == 'E'){ 
       System.out.println("I WON!"); 
       result = mazeToString(); 
       return true; 
      } 
      else{ 
      if (maze[row][col] == PATH){ 
       maze[row][col] = VISITED; 
      } else { 
       maze[row][col] = PATH; 
      } 

      if (isValid(row+1, col)){ 
       traverse(row+1, col); 
      } 

      if (isValid(row-1, col)){ 
       traverse(row-1, col); 
      } 

      if (isValid(row, col+1)){ 
       traverse(row, col+1); 

      } 
      if (isValid(row-1, col-1)){ 
       traverse(row, col-1); 
      } 
      return false; 
      } 
     } 

     private String mazeToString(){ 

        StringBuilder sb = new StringBuilder(); 
        for (int i=0; i< this.maze.length; i++) { 
        for (int j=0; j < this.maze[i].length; j++) { 
         if (maze[i][j] == '1') { 
          maze[i][j] = '#'; 
         } 
         sb.append(maze[i][j]); 
        } 
        sb.append("\n"); 
        } 
        maze[starty][startx] = 'S'; 
        return sb.toString(); 

     } 
} 

下面是輸出我從控制檯獲取（蝕）：

Enter the name of textfile to be read (add .txt): 
small.txt 
6 5 
1 1 
4 3 
1 1 1 1 1 
1 0 0 0 1 
1 0 1 0 1 
1 0 1 0 1 
1 0 1 0 1 
1 1 1 1 1 
I'm here: 1,1 :: S 
I'm here: 2,1 :: 0 
I'm here: 3,1 :: 0 
I'm here: 4,1 :: 0 
I'm here: 3,1 :: x 
I'm here: 4,1 :: x 
I'm here: 2,1 :: x 
I'm here: 1,1 :: x 
I'm here: 1,2 :: 0 
I'm here: 1,3 :: 0 
I'm here: 2,3 :: 0 
I'm here: 3,3 :: 0 
I'm here: 4,3 :: E 
I WON! 
I'm here: 2,3 :: x 
I'm here: 3,3 :: x 
I'm here: 4,3 :: E 
I WON! 
I'm here: 1,3 :: x 
I'm here: 2,2 :: # 
I'm here: 1,2 :: x 
I'm here: 2,2 :: x 
##### 
#Sxx# 
#y#y# 
#y#y# 
#y#E# 
##### 

Height: 6 Width: 5 
Starty: 1 Startx: 1 
Endy: 4 Endx: 3 
##### 
#Sxx# 
#y#y# 
#y#y# 
#y#E# 
##### 

正如你們可以清楚地看到它在找到'E'後繼續遞歸地調用iteself。

任何線索？

Answer 1

打印I WON!後，您返回true，但遞歸調用的非檢查返回值，因此當然不會停止。更改來電檢查返回值：

if (isValid(row+1, col)) { 
    if (traverse(row+1, col)) 
     return true; 
}