我已经使用深度优先搜索（Depth First Search）制作了一个迷宫生成器，它返回一个由井号和空格组成的数组来表示迷宫。例如：

char maze[height][width] ={    "#########",    "#   #   #",    "# ### # #",    "# #   # #",    "# # # ###",    "#   # # #",    "# ### # #",    "#   #   #",    "#########",};

代理总是从左上角开始（maze[1][1]），并在右下角退出（maze[7][7]）。

我现在正在尝试使用深度优先搜索来制作解算器。

问题是我是一个从初级到中级的程序员，所以我很难理解如何在C++中实现深度优先搜索，而且在迷宫中实现它对我来说更难。

我对栈、队列等有基本的了解。我也知道DFS在树中是如何工作的（基本上是理论上的），但我的主要问题是如何在一个存储在二维数组中的迷宫中实现这个算法。

我想特别学习DFS，以便我可以开始，然后我会实现其他搜索策略（例如BFS），以便开始掌握AI的使用。

编辑：我不要现成的代码！！！我想让你帮助我理解如何将伪代码转换为C++来解决迷宫问题！

回答：

因此，深度优先搜索的基本操作是：

这对于任何任意图形和树都适用。树只是一个特殊情况。你甚至可以将你的迷宫可视化为一棵树：

##########123#   ##4### # ##5#   # ## # # ####   # # ## ### # ##   #   ##########

在树和任意图形上使用此算法的唯一区别是，由于树的层次结构，树中哪些节点已被访问是隐式已知的。对于任意图形，你可能有一个这样的结构：

######187##2#6##345######

当检查节点八时，你不希望将节点一视为一个新的访问地点。

在你的迷宫中，一种记住哪些节点已被访问的方法是在遇到它们时立即用'#'填充它们。

我已经基本弄清楚了如何表示代理的位置，如何移动它等，但我的问题主要在于如何使用栈来跟踪代理去过的地方。根据我在谷歌上找到的信息，有些人保留了一个访问过的地方的栈，但我从未真正理解何时从栈中移除位置，这是我最大的困惑

栈本身并不用于跟踪哪些地方已被访问。它只跟踪当前通过迷宫的“路径”。当你到达死胡同时，节点会被从栈中移除；即使这些节点从栈中移除，它们也必须保持标记为已访问。如果移除这些节点也导致这些节点被“未访问”，那么你的搜索可能会不断尝试和重试死胡同。

我建议你首先画出几个小迷宫，并使用上面的流程图手动走一遍。这将帮助你更好地理解算法。这里有一些示例迷宫：

从O开始，到X结束####    #####      #####     ######OX#    #O X#      #O#X#     #O  #####    #####      #####     # #X#                             #####

然后考虑流程图中的每个框，思考它使用的数据，如何表示这些数据，以及如何使用这些数据在代码中实现框的动作。