java - 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();

        }
}

这是我从控制台 (eclipse) 获得的输出:

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