主题：[讨论]地图问题
Matodied
[专家分：7560] 发布于 2007-07-26 22:35:00
题目：
通过地图（map.pas）
有一次，你不小心进入了一个地带，这里没有什么能让你生存下来的东西，所以你必须赶快逃离。地图的入口是左上角，出口是右下角。
这张地图除了平地之外，还有大石头、火盆和地洞。这些东西你都不能通过，你只能通过平地。不过你身边有两辆车子，或许可以帮你一下。第一辆车子可以通过平地、大石头和地洞，第二辆车子可以通过平地和火盆地带。已知坐车必须耗掉一定的钱，而你只带了一点点钱，所以你必须尽量少坐车。
输入数据：
第1行是2个数：分别表示地图的行地带数和列地带数，接下来是一个由字母组成的矩阵(G为平地，F为火盆地带，S为石头，H为地洞)，表示地图，最后一行也是2个数，表示坐第1辆车和第2辆车经过一个地带所花的钱数。
输出：
你从左上角到右下角最少要花的钱数。
输入样例：
3 6
G G S G H F
G S G G G F
S S S F H G
11 13
输出样例：
22
回复列表 （共6个回复）
沙发
bigchen [专家分：1940] 发布于 2007-07-27 18:20:00
因为本题搜索实际上就是穷举，没有限定条件，只能穷举所有道路，而使用动态规划本题没有满足无后效性，所以我认为这题只能用穷举法，然后每次把结果与一个变量比较，每次保留小的，最后输出这个变量。
板凳
cmy28 [专家分：380] 发布于 2007-07-30 15:52:00
回溯穷举，程序我等下帮你编
3 楼
abcwuhang [专家分：1840] 发布于 2007-07-30 22:35:00
原题可转为:
把S和H转为乘坐第一辆车的钱数,G转为0(不可能坐车走平地,费钱),F转为乘坐第二辆车的钱数.
原题输入地图可转为:
0 0 11 0 11 13
0 11 0 0 0 13
11 11 11 13 11 0
于是可算出从左上角到右下角的最优路径为:(标1的部分)
1 0 0 0 0 0
1 1 1 1 1 0
0 0 0 0 1 1
4 楼
cmy28 [专家分：380] 发布于 2007-07-31 13:01:00
有道理！！我本来正想把程序发上来，看了abcwuhang的观点后觉得可以改进，你再等等……
5 楼
abcwuhang [专家分：1840] 发布于 2007-07-31 13:04:00
其实就是求从左上角到右下角的一条路径使其经过的数字和最小.
6 楼
cmy28 [专家分：380] 发布于 2007-07-31 18:01:00
Program map;
const maxn=20;
type
arr1=array[1..maxn,1..maxn]of char;
arr2=array[1..maxn,1..maxn]of integer;
btype=array[1..maxn,1..maxn]of integer;
var
m,n,cost1,cost2:integer;
a1:arr1;a2:arr2;
b:btype;
k,time,i,p,q,p1,q1,p2,q2:integer;
procedure init;
var
i,j:integer;
c:char;
begin
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(c);
a1[i,j]:=c;
read(c);
end;
readln;
end;
readln(cost1,cost2);
for i:=1 to m do
begin
for j:=1 to n do
case a1[i,j] of
'G':a2[i,j]:=0;
'S':a2[i,j]:=cost1;
'F':a2[i,j]:=cost2;
'H':a2[i,j]:=cost1;
END;
end;
end;
begin
init;
p:=m;q:=n;
for i:=1 to M do
for k:=1 to n do
b[i,k]:=32767;
b[p,q]:=a2[p,q];
repeat
p2:=p;q2:=q;
repeat
p1:=p2;q1:=q2-1;
k:=a2[p1,q1]+b[p2,q2];
if b[p1,q1]>k then b[p1,q1]:=k;
inc(q1);dec(p1);
k:=a2[p1,q1]+b[p,q];
if b[p1,q1]>k then b[p1,q1]:=k;
dec(p2);inc(q2);inc(i);
until (p2=0)or(q2>n);
if q<>1 then dec(q)
else dec(p);
until p=0;
writeln(b[1,1]);
end.
注意：本来想用回溯法，后来觉得回溯法太慢，就有修改了一个动态规划的！！
[em9][em9][em9][em9]
我来回复
您所在位置：