迷宫解算器
提问于 2015-04-16 01:38:39
我需要为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方法中添加了一组调试代码，以帮助我了解所发生的事情。无论何时我运行这个程序，它似乎都无法跟踪迷宫。我需要向此程序添加哪些内容？
回答 2
Stack Overflow用户
发布于 2015-04-16 01:48:20
除非r == size - 1为true，否则调用hasExitPath(r , c)将始终返回false。由于您从r == 0开始，并且size > 0为true，因此代码将始终以false开始。使用
if(hasExitPath(r + 1, c))
return true;而不是简单地调用hasExitPath(r + 1, c);来解决这个问题(对hasExitPath(r , c)的所有其他递归调用也是如此)。
Stack Overflow用户
发布于 2015-04-16 03:25:31
我建议不要使用递归方法，如果迷宫变得足够大，可能会出现堆栈溢出问题。我建议你做的是根据你行进的方向进行操作，并根据你是否到达交叉口或死胡同来重新评估方向。我可以给你一些代码的链接，这些代码可以解决迷宫问题，而不是使用二维数组。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29663904
复制
腾讯云开发者
