pascal 最短时间

来源:百度知道 编辑:UC知道 时间:2024/06/17 14:39:55
问题描述:
有一个N*N的矩阵,P表示平地,L表示湖泊,有个人在左上角(1,1)处,目的地在右下角(M,N)处,这个人只能向前后左右四个方向飞行,移动1格需要1单位的时间,无论一次飞多远,都要消耗1单位的时间,飞行途中不能变向,并且一次飞行后必须降落在平地上。然而他的体力也是有限的,不能无限飞行,他总共最多可以飞行的距离为D。知道以上信息后,请帮他计算最快到达目的地多需要的时间。
输入:(第一行)3个整数,m,n,d,表示是m*n的矩阵,最多能飞的距离D。
(第二行)输入矩阵。
输出:1个整数,表示他到目的地最短的时间。如果无法到达,则输出‘ERROR’
例子:输入:
4 4 2
PLLP
PPLP
PPPP
PLLP
S
输出:5
用什么方法都行

呵呵 某年GDOI的题目,过两天把程序给你,用宽搜,先占个位置

用动规?广搜?

把这道题转化为在图中寻找最短路径的题来做

DP,用F[i,j]表示到(i,j)用的最短时间