比赛场次 122
比赛名称 20120309
比赛状态 已结束比赛成绩
开始时间 2012-03-09 19:00:00
结束时间 2012-03-09 22:00:00
开放分组 全部用户
注释介绍
题目名称 飞越原野
输入输出 escapea.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarMakazeu AAAAAAAAAA 0.000 s 0.00 MiB 100
GravatarCzb。 AAAAAAAAAA 0.000 s 0.00 MiB 100
GravatarTruth.Cirno AAAATTTTTA 0.000 s 0.00 MiB 50
Gravatar苏轼 WAAAWWTTWW 0.000 s 0.00 MiB 30
GravatarLauncher WWWWWWWWWW 0.000 s 0.00 MiB 0

飞越原野

★☆   输入文件:escapea.in   输出文件:escapea.out   简单对比
时间限制:1 s   内存限制:128 MiB
【问题描述】
勇敢的法里奥出色的完成了任务之后,正在迅速的向自己的基地撤退。但由于后面有着一大群追兵,所以法里奥要尽快地返回基地,否则就会被敌人逮住。
终于,法里奥来到了最后的一站:泰拉希尔原野,穿过这里就可以回到基地了。然而,敌人依然紧追不舍。不过,泰拉希尔的地理条件对法里奥十分有利,众多的湖泊随处分布。敌人需要绕道而行,但法里奥拥有变成鹰的特殊能力,使得他能轻轻松松的飞越湖面。当然,为了保证安全起见,法里奥还是决定找一条能最快回到基地的路。
假设泰拉希尔原野是一个m·n的矩阵,它有两种地形,P表示平地,L表示湖泊,法里奥只能停留在平地上。他目前的位置在左上角(1,1)处,而目的地为右下角的(m,n)。法里奥可以向前后左右4个方向移动或者飞行,每移动1格需要1单位时间。而飞行的时间主要花费在变形上,飞行本身时间消耗很短,所以无论一次飞行多远的距离,都只需要1单位时间。飞行的途中不能变向,并且一次飞行最终必须要降落在平地上。当然,由于受到能量的限制,法里奥不能无限制的飞行,他总共最多可以飞行的距离为D。在知道了以上的信息之后,请你帮助法里奥计算一下,他最快到达基地所需要的时间。
 
【输入】
输入格式(输入文件名escape.in)
第1行是3个正整数,m(1≤m≤100),n(1≤n≤100),D(1≤D≤100)。表示原野是m·n的矩阵,法里奥最多只能飞行距离为D。
接下来的m行每行有n个字符,相互之间没有空格·P表示当前位置是平地,L则表示湖泊。假定(1,1)和(m,n)一定是平地。
 
【输出】
一个整数,表示法里奥到达基地需要的最短时间。如果无法到达基地,则输出impossible。
 
【输入输出样例】
输入(escapea.in)
4 4 2
PLLP
PPLP
PPPP
PLLP
输出(escapea.out)
5