![]() |
|
|
胜利大逃亡解题报告
|
||||
福建师大附中 林茂挺 [问题描述] 给定一个m*n的迷宫,要求在给定时间内从左上角走到右下角,但又不能碰到一些按一定规则运动的蝙蝠,求一共有多少种解法。 [分析] 这是一道比较特殊的动态规划问题,由于本题中时间为M+N-1,所以人必须保证每一时刻都向右或向下行走,因此在每一时刻,人所能到的点是固定的。我们如果撇掉蝙蝠和石柱,是可以轻易的得出解法数的。现在加上了一些石柱和不同种的蝙蝠,差别仅仅在于,石柱的位置和在某一时刻蝙蝠所在的位置对于人是无法达到的。 ![]() 由于蝙蝠是不断运动的因此我们在划分阶段的时候应采用时刻作为阶段,按斜线划分。因此,对于迷宫中的每一个点,如果这个点没有柱子且在人到达这个点的时刻这个点上没有蝙蝠,可以到达这点的方法数就应为可到达它上方的方法数加上可到达它左方的方法数之和,否则为0。 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |