java - 递归地寻找迷宫的解决路径

Question

我必须编写一个递归方法，找到从位置 (row,col) 到目标位置的路径，以 'G' 标记，并返回由字符 'U'、'R'、'D 组成的字符串'、'L'和最后的'G'，表示求解路径。

我的代码适用于从角落和边缘开始的迷宫，但不适用于像这个这样的迷宫

##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S    #
##########

当我用上面的迷宫测试我的代码时，我得到这样的输出。这条路总是向右走，直到它撞到墙上然后停下来。

Solution Path: RRRR
##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S... #
##########

我不明白如何让方法知道正确的解决方案路径。我在这里读到递归方法可以回溯到以前的调用以知道某个方向是错误的，但我不明白如何让我的方法做到这一点。

 public String findPathFrom(int row, int col){

    if(row > mapHeight || col > mapWidth){
        return "";
    }
    if(map[row][col] == '#' || map[row][col] == '.'){
        return "";
    }
    if(map[row][col] == 'G'){
        solved = true;
        return "G";
    }
    if(map[row][col] != 'S'){
        map[row][col] = '.';
    }
    if(map[row-1][col] == ' ' || map[row-1][col] == 'G'){
        return "U" + findPathFrom(row-1, col);
    }
    if(map[row][col+1] == ' ' || map[row][col+1] == 'G'){
        return "R" + findPathFrom(row, col+1) ;
    }
    if(map[row+1][col] == ' ' || map[row+1][col] == 'G'){
        return "D" + findPathFrom(row+1, col);
    }
    if(map[row][col-1] == ' ' || map[row][col-1] == 'G'){
        return "L" + findPathFrom(row, col-1);
    }
    else{
        map[row][col] = ' ';
        return "";
    }
}

我对 Java 还是个新手，如果我使用的术语不正确，我深表歉意。

Answer 1

您的算法缺少探索不同路径的逻辑。 它总是沿着它看到的第一个可用方向(上/右/下/左)前进。也就是说，当 up 和 right 可用时，它会向上，而不是向右。如果后来发现 up 没有达到解决方案，它就会停止。这是一个更简单的网格来演示问题:

###
# #
#S#
#G#
###

你的算法会上升然后卡住， 从上面无处可去。 如果它从下跌开始，情况就会有所不同。 但从长远来看，不可能知道哪个方向是最好的。 (问题不在于您检查可用空间的顺序。)

要解决此问题，请研究广度优先搜索。 这个想法是同时并行地跟踪所有可用的方向， 当任何一条路径到达解决方案时，问题就解决了。