一、题目说明

　　本题为一道纯粹的模拟题，题意是求一条最短路，但由于有很多移动的障碍物，使常规的算法都不能奏效，只有采用最原始的方法：模拟。

二、分析和说明

　　1、 最短路算法在本题中的应用：
　　 　　①、 当到达目标格子时，所有的魔鬼都将消失，这时从目标到入口的距离可用最短路算法求出。
　　 　　②、 可以事先将目标到入口的最短路求出，最短路长度的2倍即为所需时间的下界，这样可以事先排除一些无解的情况。（最短路不存在也是一种无解的情况）

　　2、 算法和数据结构：

　　对于人的走法，首先想到用深度优先或广度优先搜索。
　　深度优先搜索需要对魔鬼的行动进行多次重复的模拟，还不能首先得到最优解。广度优先搜索需要排除大量重复的状态。因此在时间上是不能忍受的，应找一种兼具两者之长，又可以两者缺点的方法。
　　有一种很容易实现的方法,使用广度优先搜索，但并不单独存储每个状态，而是将状态综合起来考虑。由于每一步的状态之间没有联系，可以考虑用一个n×m的boolean数组，表示当前时刻人是否可以到达某一个格子。由于不必再使用以前走过的情况，所以只用存储当前的可到达的状态就够了。同样，对于魔鬼的状态也只用考虑当前的情况。空间复杂度仅为O(n2)。

　　3、 需要注意的问题：
　　　　①、 魔鬼第一秒钟出现，从第二秒才开始行动。
　　　　②、 人在任意时刻都可在原地停留一秒。
　　　　③、 人进入迷宫和离开都需要一秒。

三、总结

　　模拟题并不需要太多的算法知识，主要考察选手的数据结构的应用以及编程能力。做这类题时需要有耐心和清醒的头脑，特别不能漏掉一些细节上的问题。