《迷宫问题》解题报告

大榕树 \ 信息学奥赛 \ 解题报告

《迷宫问题》解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=195
一、题目说明
　　本题为一道纯粹的模拟题，题意是求一条最短路，但由于有很多移动的障碍物，使常规的算法都不能奏效，只有采用最原始的方法：模拟。
二、分析和说明
　　1、最短路算法在本题中的应用：
　　　　①、当到达目标格子时，所有的魔鬼都将消失，这时从目标到入口的距离可用最短路算法求出。
　　　　②、可以事先将目标到入口的最短路求出，最短路长度的2倍即为所需时间的下界，这样可以事先排除一些无解的情况。（最短路不存在也是一种无解的情况）
　　2、算法和数据结构：
　　对于人的走法，首先想到用深度优先或广度优先搜索。
　　深度优先搜索需要对魔鬼的行动进行多次重复的模拟，还不能首先得到最优解。广度优先搜索需要排除大量重复的状态。因此在时间上是不能忍受的，应找一种兼具两者之长，又可以两者缺点的方法。
　　有一种很容易实现的方法,使用广度优先搜索，但并不单独存储每个状态，而是将状态综合起来考虑。由于每一步的状态之间没有联系，可以考虑用一个n×m的boolean数组，表示当前时刻人是否可以到达某一个格子。由于不必再使用以前走过的情况，所以只用存储当前的可到达的状态就够了。同样，对于魔鬼的状态也只用考虑当前的情况。空间复杂度仅为O(n2)。
　　3、需要注意的问题：
　　　　①、魔鬼第一秒钟出现，从第二秒才开始行动。
　　　　②、人在任意时刻都可在原地停留一秒。
　　　　③、人进入迷宫和离开都需要一秒。
三、总结
　　模拟题并不需要太多的算法知识，主要考察选手的数据结构的应用以及编程能力。做这类题时需要有耐心和清醒的头脑，特别不能漏掉一些细节上的问题。

作者：
来源：曙光网奥赛专题
时间：2001-08-28

上一篇：《糊涂的记者》解题报告
下一篇：《Bin Code》解题报告