java - 穿越迷宫时出现堆栈溢出错误
问题描述
我正在尝试递归遍历迷宫并且我遇到堆栈溢出错误，我理解这个问题但无法解决它。我是否需要创建一个单独的数组来保存数组中已访问的所有值，或者是否有其他方法可以更有效地使用更少的代码行？
任何建议将不胜感激。
这是输入；
5 6 // Row,Col
1 1 // Start Pos
3 4 // End Pos
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
当前代码：
public class Solve {
private static int [][] MazeArray;
private static int Rows;
private static int Cols;
private static Point end = new Point();
private static Point start = new Point();
public static void ReadFileMakeMaze() {
Scanner in = new Scanner(System.in);
System.out.print("Select File: "); // Choose file
String fileName = in.nextLine();
fileName = fileName.trim();
String Buffer = "";
String[] Buffer2;
String[] MazeBuffer;
int Counter = 0;
try {
// Read input file
BufferedReader ReadFileContents = new BufferedReader(new FileReader(fileName+".txt"));
Buffer = ReadFileContents.readLine();
MazeBuffer = Buffer.split(" ");
// Creating MazeArray according to rows and columns from input file.
Rows = Integer.parseInt(MazeBuffer[0]);
Cols = Integer.parseInt(MazeBuffer[1]);
MazeArray = new int[Rows][Cols];
// Retrieving start locations and adding them to an X and Y coordinate.
String[] StartPoints = ReadFileContents.readLine().split(" ");
start.x = Integer.parseInt(StartPoints[0]);
start.y = Integer.parseInt(StartPoints[1]);
// Retrieving end locations and adding them to an X and Y coordinate.
String[] EndPoints = ReadFileContents.readLine().split(" ");
end.x = Integer.parseInt(EndPoints[0]);
end.y = Integer.parseInt(EndPoints[1]);
while(ReadFileContents.ready()) {
Buffer = ReadFileContents.readLine();
Buffer2 = Buffer.split(" ");
for(int i = 0; i < Buffer2.length; i++) {
MazeArray[Counter][i] = Integer.parseInt(Buffer2[i]); // Adding file Maze to MazeArray.
}
Counter ++;
}
}
catch(Exception e){
System.out.println(e); // No files found.
}
System.out.println(SolveMaze(start.x, start.y));
}
public static boolean SolveMaze(int x,int y) {
Print(); // Printing the maze
if(ReachedEnd(x,y)) {
MazeArray[x][y] = 5; // 5 represents the end
System.out.println(Arrays.deepToString(MazeArray));
return true;
}else if(MazeArray[x][y] == 1 || MazeArray[x][y] == 8){
return false;
}else {
MazeArray[x][y] = 8; // Marking the path with 8's
start.x = x;
start.y = y;
// Checking all directions
if(MazeArray[x][y - 1] == 0 ) {
System.out.println("Left");
SolveMaze(x, y - 1);
}else if(MazeArray[x + 1][y] == 0) {
System.out.println("Down");
SolveMaze(x + 1, y);
}else if(MazeArray[x - 1][y] == 0 ) {
System.out.println("Up");
SolveMaze(x - 1, y);
}else if(MazeArray[x][y + 1] == 0 ) {
System.out.println("Right");
SolveMaze(x, y + 1);
}else {
System.out.println("Debug");
MazeArray[x][y] = 0;
start.x = x;
start.y = y;
}
}
return false;
}
public static boolean DeadEnd(int x, int y) {
return true; // Solution needed
}
public static boolean ReachedEnd(int x, int y) {
if(x == end.x && y == end.y) { // Check if the end has been reached.
return true;
}else {
return false;
}
}
public static void Print() {
System.out.println(Arrays.deepToString(MazeArray));
}
public static void main(String[] args) {
ReadFileMakeMaze();
}
}
解决方案
首先，就像您在问题中提到的那样，在 SolveMaze 之外创建一个静态 Collection 来保存“访问过的”节点列表肯定会有所帮助。如果之前已经访问过该节点，则无需再次检查。
其次，我相信上述代码中存在一些错误。该表未正确生成到 MazeArray[][] 中，在“//根据输入文件中的行和列创建 MazeArray”下方交换行和列。
代码也没有“找到”路径，数组被定义为 int[] array = new int[5] 但要访问它，您必须使用 array[0] --> array[4] ，当我修复迷宫是您从元素 1,1 开始，这是从左上角开始的“0”一行和一列。然后，由于 if else 语句的顺序，您遍历列表。访问每个节点后，您将节点值设置为 8。经过 4 次迭代后，代码将查看第二行底部的 0，即您上方的 [4][1] 现在是 8，因为 0 是您唯一的元素可以移动到，节点向左、向右和向下看，看到1，然后转身向上看，看到一个8。这样就完成了。
第三，不要让检查上、下、左、右一组“if else”，而只是选择“if”。这样代码将通过所有路径。然后你可以把你的 8 留在里面，事实上它不会重新运行同一个节点两次，从而不需要“访问过”的数组。（尽管作为一般规则，不建议在遍历时改变状态）
第四，我无法从上述代码中得到堆栈溢出错误，因此无法回答实际问题。
附带说明 - 使用测试和类似的事情变得微不足道，从小处着手并构建它:) 如果不确定，只需结帐 junit。