java - Java 中使用递归解决迷宫

Question

这里是作业问题，我花了几个小时编码这个问题，但我似乎无法得到正确的输出，所以我希望得到你们的一些帮助。

我的代码是:

 import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

 public class Maze {

    private int[][] grid;
    private final int TRIED = 2;
    private final int PATH = 3;

    public Maze(String fileName) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader(fileName));
        String s;
        String [] aux= new String [2];
        int x=0; 

        aux=in.readLine().split("\\s*[, .]\\s*");
        int dimensao=Integer.parseInt(aux[0]);
        String [][] gridString= new String [dimensao][dimensao];
        grid= new int[dimensao][dimensao];

         while ((s=in.readLine())!=null){
            gridString [x]=s.split("\\s*[, .]\\s*");
            x++;
        }

        for (int i=0;i<gridString.length;i++){
            for(int j=0;j<gridString[0].length;j++){
                switch (gridString[i][j]) {
                    case "true":
                        grid[i][j]=1;
                        break;
                    case "false":
                        grid[i][j]=0;
                        break;
                }
            } 
            }
    }
    public boolean traverse(int row, int column) {
        boolean done = false;
        if (valid(row, column)) {
            grid[row][column] = TRIED; // this cell has been tried
            if (row==grid.length-1)
                done = true; // the maze is solved
             else {
                done = traverse(row + 1, column); // down
                if (!done) 
                    done = traverse(row, column + 1); // right
                if (!done) 
                    done = traverse(row - 1, column); // up
                if (!done) 
                    done = traverse(row, column - 1); // left
            }
            if (done) // this location is part of the final path
                grid[row][column] = PATH;

        }
        return done;
    }

    private boolean valid(int row, int column) {
        boolean result = false;
        if (row >= 0 && row < grid.length
                && column >= 0 && column < grid[row].length) // check if cell is not blocked and not previously tried
        {
            if (grid[row][column] == 1) {
                result = true;
            }
        }
        return result;
    }
    public String toString (){
        String result = "\n";
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                result += grid[row][column] + "";
            }
            result += "\n";
        }
        return result;
    }
    public String [][]transformMatrix (int [][]array ){
        String [][] matrizChar= new String [array.length][array[0].length];
        for (int i=0; i<array.length; i++)
            for(int j=0; j<array[0].length;j++){
            if (array[i][j]==1)
                matrizChar[i][j]="*";
            else matrizChar[i][j]="-";
            }
             return matrizChar;   

    } 

}

另一个类是:

 public static void main(String[] args) throws IOException {
        {
            Maze labyrinth = new Maze("rede.txt");
            System.out.println(labyrinth);
            boolean done=labyrinth.traverse(0, 0);
            if (labyrinth.traverse(0, 0)) {
                System.out.println("The maze was successfully traversed!");
            } else {
                System.out.println("There is no possible path.");
            }

            System.out.println(labyrinth);

        }
    }
}

我使用的文本输入是

5

真，假，真，假，假

真，假，真，真，真

假，假，假，假，真

真，真，假，真，真

假，假，假，真，假

它生成数组:

1 0 1 0 0

1 0 1 1 1

0 0 0 0 1

0 0 0 1 0

0 0 0 1 0

因为它将输入文本文件转换为整数数组。

现在我的问题是它像这样解决迷宫

2 0 1 0 0

2 0 1 1 1

0 0 0 0 1

1 1 0 1 1

0 0 0 1 0

什么时候应该这样解决

2 0 3 0 0

2 0 3 3 3

0 0 0 0 3

1 1 0 3 3

0 0 0 3 0

它还说迷宫没有解决方案，所以我猜测问题依赖于“遍历”方法，但我真诚地无法找出错误在哪里。非常感谢帮助!

Answer 1

看起来您的问题是来自 traverse() 方法内的 return 语句。走过这个:

• 当 (0,0) valid(row,column) 为 true 时。
• 设置等于 2，向下移动 1 并调用 traverse(1,0)。
• 当(1,0)有效(行，列)为真时
• 设置等于 2，向下移动一位并调用 traverse(2,0)。
• 当 (2,0) valid(row,column) 为 false 时
• 返回完成(即 false)
• 所有其他 if 语句都返回 false(周围值无效)
• 程序结束。

程序

public boolean traverse(int row, int column) {
            boolean done = false;
            if (valid(row, column)) {
                grid[row][column] = TRIED; // this cell has been tried
                if (row==grid.length-1)
                    done = true; // the maze is solved
                 else {
                    done = traverse(row + 1, column); // not valid
                    if (!done) 
                        done = traverse(row, column + 1); // not valid
                    if (!done) 
                        done = traverse(row - 1, column); // not valid
                    if (!done) 
                        done = traverse(row, column - 1); // not valid
                }
                if (done) // this location is part of the final path
                    grid[row][column] = PATH;

            }
            return done;  
        }

还值得注意

你的起始位置 (0, 0) 没有到达终点的合法路径，所以你自然会得到它作为答案。如果你想找到合法的路径，那么要么遍历所有可能的起点，要么将起点放在实际的可完成路径上的某个位置。