迷宫解决程序的 StackOverflow 错误

Question

目前我正在尝试解决一个程序，该程序确定是否可以解决迷宫，如果迷宫是可解决的，它应该打印出通过迷宫路径的步数。起始位置和结束位置以及迷宫在以下格式的输入文件中给出：

第 1 行：测试用例(N)

对于每N行，第一行将包含迷宫的大小、开始位置和结束出口位置。然后迷宫的视觉描述也将出现在输入文件中

例如，这个挑战的示例输入是：

3
6 7 0 0 5 6
1110111
1011101
1001001
1011101
1000001
1111110
3 3 2 0 0 2
111
110
111
5 5 1 0 3 1
01111
11001
01001
01001
01111

迷宫的确切规则是 0 是无法穿透的墙壁，1 是自由行走 space 可以四处走动。结束位置也没有用任何特殊字符标记，而是给我们的位置。

以下代码是我应对挑战的方法，但显然不起作用：

import java.io.*;
import java.util.*;
public class Maze
{

    public static void main(String[] args) throws FileNotFoundException
    {
        Scanner sc = new Scanner(new File("maze.txt"));
        int tc = sc.nextInt();
        for(int p  = 0; p < tc; p++ ) {
            int rows = sc.nextInt();
            int cols = sc.nextInt();
            int startRow = sc.nextInt();
            int startCol = sc.nextInt();
            int endRow = sc.nextInt();
            int endCol = sc.nextInt();
            sc.nextLine();
            char[][] maze = new char[rows][cols];
            for(int i = 0; i < rows; i++) {
                String s = sc.nextLine();
                for(int j = 0; j < cols; j++) {
                    maze[i][j] = s.charAt(j);
                }
            }

            if(solvable(maze,startRow,startCol,endCol,endRow)) {
                int count = 0;
                for(char[] arr : maze) {
                    for(char elem: arr) {
                        if(elem == 'x') count++;
                    }
                }
                System.out.println("It takes " + count + " steps to solve the maze");
            }else {
                System.out.println("Unsolvable");
            }


        }

    }


    public static boolean solvable(char[][] maze,int row, int col,int finishRow, int finishCol) {

        if(row < 0 || col < 0 || row >maze.length - 1 || col > maze[0].length - 1) {
            return false;
        }
        if(row == finishRow && col == finishCol) {
            return true;
        }
        if(maze[row][col] == 0) {
            return false;
        }
        char c = maze[row][col];
        maze[row][col] = 'x';
        if(solvable(maze,row + 1,col,finishRow,finishCol)) {
            return true;
        }
        if(solvable(maze,row - 1,col,finishRow,finishCol)){
            return true;
        }
        if(solvable(maze,row ,col + 1,finishRow,finishCol)) {
            return true;
        }
        if(solvable(maze,row,col - 1,finishRow,finishCol)) {
            return true;
        }
        maze[row][col] = c;
        return false;


    }

}

如标题所示，该程序产生堆栈溢出错误。我正在合并解决迷宫的通用算法，而不是合并洪水填充算法。我需要确定我的递归方法中可解决的缺陷。请注意，这是一个竞争激烈的编程环境，因此从 java 的 object 面向编码是不方便的。

Answer 1

问题是solvable中的无限递归。这是为什么？为什么它永远不会终止？让我们仔细看看它是如何工作的：

return false如果位置无效
return true如果位置是目标
return false如果位置是开始
- 这有点奇怪，但无论如何，让我们继续
此时我们知道当前位置是有效的
保存当前位置的旧值，并用'x'
尝试向所有可能的方向移动
恢复当前位置的原始值

这个逻辑的漏洞在哪里？

什么时候使用标记'x'？ -> 哈！

如果不使用标记'x'，会发生什么？ -> 哈！

想象一下这是迷宫，算法总是先检查向下的路径，然后再检查其他方向：

#####
#S E#
# ###
# ###
#####

算法会先从S开始，一直到底部。在底部有一条上去的路，所以它更上一层楼。在那里，有一条路可以往下走，所以它会往下走。它会永远上下波动。

所以解决方案是使用 'x' 标记来避免永远探索相同的位置。

迷宫解决程序的 StackOverflow 错误

StackOverflow error for maze solving program

java

recursion

infinite-recursion