原文链接：http://www.mydrs.org/program/list.asp?id=299
[问题描述]给定一个m*n的迷宫，要求在给定时间内从左上角走到右下角，但又不能碰到一些按一定规则运动的蝙蝠，求一共有多少种解法。
[分析]
这是一道比较特殊的动态规划问题，由于本题中时间为M+N-1，所以人必须保证每一时刻都向右或向下行走，因此在每一时刻，人所能到的点是固定的。我们如果撇掉蝙蝠和石柱，是可以轻易的得出解法数的。现在加上了一些石柱和不同种的蝙蝠，差别仅仅在于，石柱的位置和在某一时刻蝙蝠所在的位置对于人是无法达到的。
由于蝙蝠是不断运动的因此我们在划分阶段的时候应采用时刻作为阶段，按斜线划分。因此，对于迷宫中的每一个点，如果这个点没有柱子且在人到达这个点的时刻这个点上没有蝙蝠，可以到达这点的方法数就应为可到达它上方的方法数加上可到达它左方的方法数之和，否则为0。
本题还由于蝙蝠旋转时不花时间且蝙蝠一开始还有可能在石柱上，因此还需考虑许多特殊情况。
[小结]
本题主要特点是采用斜线为阶段的动态规划，并且程序要对许多特殊情况进行处理。
作者：林茂挺
来源：福建师大附中
时间：2001-12-14
上一篇：
下一篇：2001福建组队赛试题及数据