Pascal经典算法详解 – 骑士游历问题

设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。

输入：&nbsp&nbsp&nbsp&nbspm,n,x1,y1,x2,y2&nbsp(分别表示m,n、起点坐标和终点坐标)输出：&nbsp&nbsp&nbsp&nbsp路径数目（若不存在，则输出0）【分析】&nbsp&nbsp&nbsp本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。&nbsp&nbsp&nbsp&nbsp从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。&nbsp&nbsp&nbsp&nbsp阶段i：中国象棋马当前的列位置（x1≤i≤x2）&nbsp&nbsp&nbsp&nbsp状态j：中国象棋马在i列的行位置（1≤i≤m）&nbsp&nbsp&nbsp&nbsp状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目&nbsp&nbsp&nbsp&nbsp具体算法如下：

fillchar(map,sizeof(map),0);
map[x1,y1]←1；
for i←x1+1 to x2 do
  for j←1 to m do
     map[i,j]←map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];
writeln(map[x2,y2]);

详细代码：

program qishiyouli;
const
  maxm=50;
  maxn=50;
var
  m,n,x1,y1,x2,y2:integer;
  i,j,k,x,y:integer;
  map:array[-2..maxm+2,-2..maxn+2] of extended;
begin
fillchar(map,sizeof(map),0);
readln(m,n,x1,y1,x2,y2);
map[x1,y1]:=1;
for i:=x1+1 to x2 do
  for j:=1 to m do
      map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];
writeln(map[x2,y2]:0:0);
end.