使用图的迷宫求解

Question

嘿，我当时参加了当地的编程比赛，他们问我这个问题，我无法做到这一点，请帮助我。

编写一个程序，该程序从迷宫的大小和迷宫本身的文件中加载。为了建模迷宫，我们使用指定开始单元格的字符“ s”。指定自由单元格，“＃”是墙壁，“ f”是最终单元格。编写一个程序，该程序将找到从开始单元到最终单元格的路径。您可以认为在迷宫中，有一个机器人服从命令，因此，对于以下迷宫，机器人应收到以下命令：向上，向上，向上，右，右，下，下，向下。

迷宫1文本文件

5 5
#####
#...#
#.#.#
#S#T#
#####

迷宫2文本文件

4 5
#.#.#
#.#.#
#S#T#
#####

一般编写您的程序（迷宫最大输入最多可以是200x200）。

帮助您将不胜感激。我只是一个崛起的大约，所以如果您能为我提供代码，那么我可以理解，他们会再次做到这一点。

Answer 1

找到一条路径的一种方法：

1. 要检查单元格的队列，并从那里到目的地为每个单元格的步骤计数。
2. 将终端单元的计数设置为0，然后将其添加到队列中。
3. 虽然队列不是空的：
   1. 从队列中获取单元格。
   2. 对于每个自由的邻居单元，将当前单元的计数 + 1与邻居单元的计数进行比较。如果较少，如果邻居单元还没有计数，请将邻居单元的计数设置为当前单元的计数 + 1，然后将邻居单元格添加到队列中。

一旦队列的空白，迷宫中的每个自由单元（可以从目的地达到）将在通往目的地的最短路径中的步骤数。如果单元格没有计数，则没有从中到达目的地的路径。

如果起始单元有计数，

1. 获取开始单元的计数。
2. 检查每个邻居单元是否计数（计数-1）。那里 将要 做一个，这是路径中的下一步。记录到该单元格的方向，然后获取该单元格，如果不是目的地，请使用该单元重复步骤2。

我将其保留给您，以弄清楚如何加载迷宫。这是所有这些简单的部分。

Answer 2

如果您不知道要搜索什么：http://en.wikipedia.org/wiki/pathfinding#sample_algorithm这包含更多信息：http://www.astrolog.org/labyrnth/algrithm.htm

Answer 3

该代码在这里写得太多了，但是解决迷宫的最常见方法是朝一个方向出发，并且在右转的每个转弯处都可以右转。

只要开始和出口位于周围的四个墙壁之一中，就可以保证工作。对于没有沿着墙壁的开始和退出的迷宫，这是递归中的练习。

根据起点，看看您可以根据代码提出什么！

Hth，詹姆斯