文档介绍：分析:我们已经通过动规找到了最短路径长度,要输出最短路径,其实就是找各个城市的的后续城市。
设一个数组l:array[1..7] of note来存7个城市的后续城市。
Note=record
h:ingter;
End;
在找最短路径时,找到一个最小值就给该城市赋上相应的后续
A
B
C
D
E
F
G
6
4
5
3
4
7
5
3
5
4
1
2
3
4
5
6
7
求最短路径
for i:=n-1 downto 1 do
begin
min:=maxint;
for j:=i to n do
if (d[i,j]<>0)and(f[j]+d[i,j]<min)
then begin
min:=d[i,j]+f[j];
l[i].h:=j;
end;
f[i]:=min;
end;
writeln(f[1]);
write(chr(1+64));
p:=1;
repeat
write(‘-’,chr(l[p].h+64));
p:=l[p].h;
until p=7;
{存当前节点的后续节点}
{先输出A}
{从后续城市中找该城市的后续城市}
回顾二. 马拦过河卒
实例
[问题描述]: 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。
棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。
[输入]: 键盘输入 B点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错}
[输出]: 屏幕输出 一个整数(路径的条数)。
[输入输出样例]: 输入: 6 6 3 2 输出: 17
步骤1:用F(X,Y)表示到棋盘上每个阶段(X,Y)的路径条数;
步骤2:状态转移方程:
步骤3:以自底向上的方法来计算最优解
分析:此题不涉及最值问题,但存在重叠子问题,本是一道递推题,我们也可用动规思想来解题。
阶段:棋盘上的每个可走的点;
每个阶段的求解;
F(X,Y)= F (X-1,Y)+ F(X, Y-1)
其中,F(0,0 )=1
F (0,Y)=1 直到b[0,Y]不可走
F (X,0)=1 直到b[x,0]不可走
1
1
1
1
1
1
2
3
4
5
6
A(0,0)
1
2
3
4
5
6
B(6,6)
C(3,2)
1
1
1
0
0
0
0
0
0
1
1
2
3
0
0
1
1
0
2
5
0
0
1
1
3
8
0
0
0
0
0
0
1
0
0
0
0
0
3
11
14
17
3
3
program dgqp;
var
n,m,x,y,i,j:integer;
f:array[-1..20,-1..20] of integer;
b:array[-1..20,-1..20] of boolean;
begin
read(n,m,x,y); fillchar(f,sizeof(f),0); fillchar(b,sizeof(b),false);
for i:=0 to n do
for j:=0 to m do
b[i,j]:=true;
b[x,y]:=false; b[x-1,y+2]:=false;
b[x-2,y+1]:=false; b[x-2,y-1]:=false; b[x-1,y-2]:=false; b[x+1,y-2]:=false;
b[x+2,y-1]:=false; b[x+2,y+1]:=false; b[x+1,y+2]:=false;
for i:=0 to n do
if b[i,0]
then f[i,0]:=1 else break;
for j:=0 to m do
if b[0,i]
then f[0,j]:=1 else break;
for i:=1 to n do
for j:=1 to m do
if b[i,j]
then f[i,j]:=f[i-1,j]+f[i,j-1];
writeln(f[n,m]);
end.
动态规划(三)
常见题型
最长公