迹忆客 专注技术分享

迷宫求解算法是计算机科学和人工智能中的经典问题。

C++ 迷宫求解器

迷宫求解算法旨在通过仅在四个罗盘方向上移动来找到从起点到终点的最短路径。 该算法维护两组信息：打开列表，其中包含所有尚未访问的节点，以及关闭列表，其中包含所有已访问过的节点。

为了找到迷宫中从一个节点到另一个节点的路径，我们需要做这些事情：

• 检查开放节点是否与当前节点相邻（左或右）。
• 如果不是，则检查闭合节点是否与当前节点相邻（左或右）。
• 如果不是，请返回一步并再次执行步骤 1 和 2。

迷宫求解算法示例：

#include <iostream>
using namespace std;
bool demo_maze(char maze[9][9], bool sam[9][9],
int x,
int y,
int u,
int v)
{
    if(x == u && y == v)
    {
        sam[x][y] = true;
        for(int t = 0; t <= u; t++)
        {
            for(int f = 0; f <= v; f++)
            {  cout << sam[t][f] << " ";
            }
            cout << endl;
        }  cout << endl;
        return true;
    }
    if(x > u || y > v)
        return false;
    if(maze[x][y] == 'X')
        return false;
    sam[x][y] = true;
    bool right = demo_maze(maze, sam, x, y + 1, u, v);
    bool down = demo_maze(maze, sam, x + 1, y, u, v);
    sam[x][y] = false;
    if(right || down)
        return true;
    return false;
}
int main()
{
    char maze[9][9] = {"0000", "00X0", "000X", "0X00"};
    bool sam[9][9] = {0};
    int u = 3, v = 3;
    bool ans = demo_maze(maze, sam, 0, 0, u, v);
}

单击此处检查上述代码的工作情况。

C++ 中迷宫求解器的使用

迷宫求解算法可用于多种用途，包括国际象棋、扫雷以及寻找穿过迷宫或地图上其他障碍物的路径。 当您迷路并寻找走出森林或迷宫的路时，该算法可以决定走哪条路！

迷宫求解算法也用于 2D 游戏，但由于其计算复杂性，它会比其他算法花费更多的时间。 它使用递归函数检查玩家的坐标，然后将其移动到下一个位置。

递归函数直接或间接调用自身。 它可以用来解决递归问题，也可以用来解决解不容易表达为短循环的问题。