Решатель лабиринта Java

Мне нужно написать программу решения лабиринта для APCS, которая включает текстовую матрицу из единиц и нулей. Мне нужно написать код, который находит путь, если он есть, от координаты 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, чтобы помочь мне понять, что происходит. Каждый раз, когда я запускаю программу, кажется, что она не может проследить лабиринт. Что мне нужно добавить в эту программу?


java solver maze
person Jonas Anthony Salcedo    schedule 16.04.2015    source источник
comment
Может быть, более полезно удалить код, чем добавить код. Начните с тестирования очень и очень простого лабиринта и убедитесь, что ваша структура данных именно такая, как вы этого хотите. Когда вы сможете решить очень простой лабиринт, увеличьте сложность.   -  person Patricia Shanahan    schedule 16.04.2015

Ответы (2)


arrow_upward
3
arrow_downward

вызов hasExitPath(r , c) всегда будет возвращать false, если r == size - 1 не истинно. Поскольку вы начинаете с с r == 0, а size > 0 истинно, код всегда будет иметь результат false. Использовать

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

вместо простого вызова hasExitPath(r + 1, c); для решения этой проблемы (то же самое для всех других рекурсивных вызовов hasExitPath(r , c)).

person Paul    schedule 16.04.2015
comment
Во-первых, матрицы возвращают истину, но на этом все они возвращают истину, кроме той, что была в начале. - person Jonas Anthony Salcedo; 16.04.2015
comment
возможно лабиринт неправильно разбирается. если вы попытаетесь попасть из 0,0 в нижнюю часть лабиринта, а не вправо от лабиринта, фактически все лабиринты, кроме первого, имеют выход. - person Paul; 16.04.2015

arrow_upward
0
arrow_downward

Я бы не советовал использовать рекурсивный подход, если лабиринт станет достаточно большим, у вас может возникнуть проблема с переполнением стека. я бы посоветовал вам действовать в соответствии с направлением, в котором вы движетесь, и переоценивать направление в зависимости от того, достигнете ли вы перекрестка или тупика. Я могу дать вам ссылку на код, который работает с проблемой лабиринта, но не использует 2d-массив.

person Taher    schedule 16.04.2015