0

嘿，我参加了当地的编程比赛，他们问了我这个我做不到的问题，请帮助我解决这个问题。

编写一个程序，从一个迷宫大小的文件加载，然后是迷宫本身。为了模拟迷宫，我们使用字符“S”来指定起始单元格“.”。指定空闲单元格，“#”是墙，“F”是最后一个单元格。编写一个程序，找出从起始单元到最终单元的路径。你可以认为迷宫中有一个服从命令的机器人，那么对于下面的迷宫，机器人应该收到以下命令：上、上、右、右、下、下。

迷宫 1 文本文件

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

迷宫 2 文本文件

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

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

帮助将不胜感激。我只是一个正在升起的大二学生，所以如果你能给我提供代码，那么我就能理解它，他们会自己再做一次。

4

3 回答 3

3

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

于 2010-11-14T05:01:01.663 回答
2

查找路径的一种方法：

  1. 有一个要检查的单元格队列，以及从那里到目的地的每个单元格的步数。
  2. 将结束单元格的计数设置为 0，并将其添加到队列中。
  3. 当队列不为空时：
    1. 从队列中获取一个单元格。
    2. 对于每个空闲的相邻单元，将当前单元的计数 + 1 与相邻单元的计数进行比较。如果小于，或者如果相邻单元格还没有计数，则将相邻单元格的计数设置为当前单元格的计数 + 1，然后将相邻单元格添加到队列中。

一旦队列为空，迷宫中的每个空闲单元（可以从目的地到达）都将具有到目的地的最短路径中的步数。如果一个单元格没有计数，则没有从它到目的地的路径。

如果起始单元格有计数，

  1. 获取起始单元格的计数。
  2. 检查每个相邻小区的计数（计数 - 1）。会有一个，这是路径的下一步。记录到该单元格的方向，然后获取该单元格，如果它不是目的地，则对该单元格重复步骤 2。

我将由您来决定如何加载迷宫。这是所有这一切的简单部分。

于 2010-11-14T04:35:19.483 回答
0

代码太多，这里就不写了，不过最常见的解决迷宫的方法是朝一个方向出发，每次可以右转，右转。

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

以此为起点，看看你能想出什么代码！

HTH，詹姆斯

于 2010-11-14T04:22:47.357 回答