java - 迷宫求解器java

Question

我需要为 APCS 编写一个迷宫求解程序，其中涉及基于文本的 1 和 0 矩阵。我必须编写代码来找到一条从坐标 0,0 到右侧任意位置的路径(如果有的话)。这是我到目前为止所拥有的

public class Maze {
    private int[][] maze;
    private int sizes = 0;
    private boolean[][] checked;

    public Maze(int size, String line) {
        checked = new boolean[size][size];
        sizes = size;
        out.println(sizes - 1);
        Scanner joe = new Scanner(line);
        maze = new int[size][size];
        for (int x = 0; x < size; x++) {
            for (int y = 0; y < size; y++) {
                maze[x][y] = joe.nextInt();
            }
        }
    }

    public boolean hasExitPath(int r, int c) {
        boolean solved = false;
        boolean wall = false;

        if (r == sizes - 1) {
            solved = true;
            return solved;
        }

        maze[r][c] = 2;
        if (maze[r + 1][c] == 1) {
            out.println("down");
            hasExitPath(r + 1, c);
        }else if (maze[r][c + 1] == 1) {
            out.println("left");
            hasExitPath(r, c + 1);
        }else if (maze[r - 1][c] == 1) {
            out.println("up");
            hasExitPath(r - 1, c);
        }else if (maze[r][c - 1] == 1) {
            out.println("right");
            hasExitPath(r, c - 1);
        }
        System.out.println(r + " " + c);
        return solved;
    }

    public String toString() {
        String output = "";
        for (int y = 0; y < sizes; y++) {
            for (int x = 0; x < sizes; x++) {
                output = output + maze[y][x];
            }
            output = output + "\n";
        }
        return output;
    }
}

这是主类

public class MazeRunner {
    public static void main(String args[]) throws IOException {
        Scanner mazeinfo = new Scanner(new File("maze.dat"));

        int size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        String b = mazeinfo.nextLine();
        Maze m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));
    }
}

这是需要解决的迷宫的图像

https://drive.google.com/file/d/0BzE3Cu7SjRlNdzRHYjM4UzZkY00/view?usp=sharing

我在 hasExitPath 方法中添加了一堆调试代码来帮助我了解发生了什么。每当我运行该程序时，它似乎都无法追踪迷宫。我需要向该程序添加什么？

Answer 1

调用 hasExitPath(r , c) 将始终返回 false，除非 r == size - 1 为 true。由于您从 r == 0 开始，并且 size > 0 为 true，因此代码的结果将始终为 false。使用

if(hasExitPath(r + 1, c))
     return true;

而不是简单地调用 hasExitPath(r + 1, c); 来解决此问题(对于 hasExitPath(r , c) 的所有其他递归调用相同) .