飞越原野。(escape.1s,64MB)
Background
Special for beginners, ^_^
Description
在一片广阔的土地上有一个鸟人,他需要从这里穿过原野回到基地。这片原野上有平地(P)。有湖泊(L)。因为鸟人可以飞,所以有的时候,他可以飞越湖泊。现在,鸟人需要用最快的时间回到基地。
假设原野是一个mxn的矩阵,有两种地形,用P和L表示。鸟人只能停留在平地上。他目前处在(1,1)这个位置,而目的地是(m,n)。他可以向上、下、左、右四个方向移动,或者飞行每移动一格需要1个单位时间。而飞行无论飞多远,都只需要1个单位时间,飞行的途中不可以改变方向。也就是说,飞行也只能是上、下、左、右四个方向,并且一次飞行最终必须降落在平地上。当然,受到能量的限制,鸟人不能无限制地飞行,他总共最多可以飞行的距离为 D。
Format
Input
第1行是3个整数m、n和D,3个数都不超过100。下面是一个mxn的字符矩阵,表示原野。
Output
输出一行一个整数表示最短时间。如果无法到达,输出"impossible"
Sample 1
Input
4 4 2
PLLP
PPLP
PPPP
PLLP
Output
5
Source
课课通
信息
- ID
- 1005
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 42
- 已通过
- 2
- 通过率
- 5%
- 上传者