Question

骑士巡游问题 pascal

。。。。。。。

Answer 1

是DP，楼下不要误人子弟。
【骑士游历问题】
设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。
输入：
m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)
输出：
路径数目（若不存在，则输出0）
【分析】
本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。（专为楼下设计）
从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。
阶段i：中国象棋马当前的列位置（x1≤i≤x2）
状态j：中国象棋马在i列的行位置（1≤i≤m）
状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目

附标程：

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.

Answer 2

搜

Answer 3

骑士巡游<>骑士游历

典型的DFS