时间戳

首页 > 解决方案 > 如何从迷宫求解算法中的错误路径返回？（爪哇）

java - 如何从迷宫求解算法中的错误路径返回？（爪哇）

问题描述

我一直在尝试在 java 中创建一个迷宫求解算法。我试图用回溯递归来做到这一点。这是我的代码：

public static boolean solver(String[][] maze, int i, int j){
    display(maze);//prints maze
    System.out.println();
    maze[i][j] = "*";
    if(maze[i][j+1] == "E" || maze[i][j-1] == "E" || maze[i+1][j] == "E" || maze[i-1][j] == "E")
        display(maze);
    else if(maze[i][j+1] != " " && maze[i][j-1] != " " && maze[i+1][j] != " " && maze[i-1][j] != " "){
        maze[i][j] = " ";
        return false;
    }
    if(maze[i][j+1] == " ")
        if(!solver(maze,i,j+1))
            maze[i][j] = " ";
    if(maze[i][j-1] == " ")
        if(!solver(maze,i,j-1))
            maze[i][j] = " ";
    if(maze[i+1][j] == " ")
        if(!solver(maze,i+1,j))
            maze[i][j] = " ";
    if(maze[i-1][j] == " ")
        if(!solver(maze,i-1,j))
            maze[i][j] = " ";
    return true;
}

这是主要方法：

String[][] maze = {{"#","S","#","#","#","#","#","#","#","#","#","#","#"},
                   {"#"," "," "," "," "," ","#"," "," "," "," "," ","#"},
                   {"#"," ","#","#","#","#","#"," ","#","#","#"," ","#"},
                   {"#"," "," "," "," "," ","#"," ","#"," ","#"," ","#"},
                   {"#"," ","#","#","#"," ","#"," ","#"," ","#"," ","#"},
                   {"#"," "," "," ","#"," ","#"," "," "," ","#"," ","#"},
                   {"#"," "," "," ","#"," ","#"," "," "," ","#"," ","#"},
                   {"#"," ","#"," ","#"," "," "," "," "," "," "," ","#"},
                   {"#","#","#"," ","#","#","#","#","#","#","#","#","#"},
                   {"#"," "," "," ","#"," "," "," "," "," "," "," ","#"},
                   {"#"," ","#","#","#"," ","#","#","#","#","#"," ","#"},
                   {"#"," "," "," "," "," ","#"," "," "," "," "," ","#"},
                   {"#","#","#","#","#","#","#","#","#","#","#","E","#"}};
solver(maze,1,1);

这个算法可以解决一个迷宫，但是这段代码中有一个错误，我无法解决这个错误。

输出：

#S###########
#*****#     #
# ##### ### #
#     # # # #
# ### # # # #
#   # #   # #
#   # #   # #
# # #       #
### #########
#   #       #
# ### ##### #
#     #     #
###########E#

#S###########
#***  #     #
#*##### ### #
#     # # # #
# ### # # # #
#   # #   # #
#   # #   # #
# # #       #
### #########
#   #       #
# ### ##### #
#     #     #
###########E#

如您所见，它以这种方式出现，但在返回时并不能正确移除星星。

我该如何解决这个错误？

标签： javarecursionbacktracking

解决方案

也许它有助于从“迷宫”的特定表示中抽象出来，并将（完美）迷宫视为二维网格上无向图的生成树。然后你只需要在那个网格上实现你喜欢的任何寻路算法。“解决”迷宫只是在网格边界上的两个顶点之间找到一条路径。

我已经基于这个图论视图实现了许多迷宫生成和寻路算法，你可以在这里找到我的代码和演示应用程序：

https://github.com/armin-reichert/mazes

推荐阅读