c++ - 使用递归迷宫最短路径

Question

首先，我想指出，我之前发布过同样的问题，但没有找到正确的答案，很抱歉重复这个问题。

请注意，我必须在此处使用递归。我知道最短路径通常是使用 BFS 找到的，这不是递归的，但我需要知道如何递归完成。

我正在开发一款 rouge 游戏，我的一个怪物表现得像这样。在迷宫中，如果怪物可以在 15 步或更短的距离内到达玩家，则可以做出最佳移动。为了实现这一点，我编写了一个小程序，基本上模仿我的游戏中将要发生的事情。我的程序的工作方式是能够检查 x 步移动是否能让他到达目的地。我唯一不确定的是如何迈出第一步，这样我就可以将该信息传递给我的怪物移动功能。这是我到目前为止编写的程序。

我的一位同学建议用不同的值填充空白区域并找到路径，但我不明白他的意思。有人可以向我解释如何做到这一点吗？

#include <iostream>

using namespace std;



bool pathExists(char maze[][10], int sr, int sc, int er, int ec, int distance) {
    if (maze[sr][sc] != '.')
        return false;

    if (sr == er  &&  sc == ec)
        return true;

    if(distance == 15) {
        cout<<"Cant make it in 15 steps"<<endl;
        return false;
    }
    maze[sr][sc] = '@';  // anything non-'.' will do

    if (pathExists(maze, sr-1, sc, er, ec, distance+1))
        return true;
    if (pathExists(maze, sr+1, sc, er, ec,distance+1))
        return true;
    if (pathExists(maze, sr, sc-1, er, ec, distance+1))
        return true;
    if (pathExists(maze, sr, sc+1, er, ec, distance+1))
        return true;

    return false;
}

int main() {
    char maze[10][10] = {
        { 'X','X','X','X','X','X','X','X','X','X'},
        { 'X','.','.','.','.','.','.','.','.','X'},
        { 'X','.','X','X','X','X','.','X','X','X'},
        { 'X','.','.','X','.','X','.','.','.','X'},
        { 'X','.','.','X','.','.','.','X','.','X'},
        { 'X','.','X','X','.','X','X','X','.','X'},
        { 'X','.','X','.','.','.','.','X','X','X'},
        { 'X','.','.','X','X','.','X','X','.','X'},
        { 'X','.','.','x','.','.','.','.','.','X'},
        { 'X','X','X','X','X','X','X','X','X','X'}
    };

    if (pathExists(maze, 8,8, 1,1,0))
        cout << "Solvable!" << endl;
    else
        cout << "Out of luck!" << endl;
}

Answer 1

您的算法运行良好。唯一缺少的是如果测试路径不成功，则在 pathExist() 中恢复 '.' :

    ...
    if(pathExists(maze, sr, sc + 1, er, ec, distance + 1))
        return true;

    maze[sr][sc] = '.'; //<===========  add this to restore the maze state

    return false;
    }

如果没有这一行，您寻找正确路径的失败尝试将用 '@' 填充数组，这样后续探索将找不到任何可用的 '.'。了。

顺便说一下，由于 [8][3] 位置的 'x'，您在问题中发布的迷宫在 15 次尝试后无法解决。

补充说明:

您还询问了这是如何工作的。事实上，没有“@”技巧的递归算法没有内存。所以在递归调用中，它不记得它是从哪里来的，这将导致根据以下模式无限递归:
将当前位置暂时更改为“@”的事实就好像您要标记当前正在探索的路径的不同单元格一样:

请注意，如果您在最后打印出网格，您将看到找到的完整路径(删除了有问题的“x”):