题目概述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
解题思路
使用广搜，注意地图边界和马跳的方向即可。可以采用for代替8个if来减少要码的字。注意栈的读写。
时间复杂度:O(n*m)
空间复杂度:O(n*m)
源程序
const d:array[1..2,1..8]of longint=((-2,-2,-1,-1,1,1,2,2),(1,-1,2,-2,2,-2,1,-1)); var a:array[1..1002,1..1002]of longint; b:array[1..250020,1..2]of longint; n,m,x,y,i,j,top,tail:longint; s:string; begin readln(n,m,x,y); b[1,1]:=x; b[1,2]:=y; for i:=1 to n do for j:=1 to m do a[i,j]:=-1; a[x,y]:=0; top:=0; tail:=1; while top<tail do begin inc(top); if top>250000 then top:=1; for i:=1 to 8 do if (b[top,1]+d[1,i]>=1)and(b[top,1]+d[1,i]<=n) and(b[top,2]+d[2,i]>=1)and(b[top,2]+d[2,i]<=m) and(a[b[top,1]+d[1,i],b[top,2]+d[2,i]]=-1)then begin inc(tail); if tail>250000 then tail:=1; b[tail,1]:=b[top,1]+d[1,i]; b[tail,2]:=b[top,2]+d[2,i]; a[b[tail,1],b[tail,2]]:=a[b[top,1],b[top,2]]+1; end; end; for i:=1 to n do begin for j:=1 to m-1 do begin s:=''; str(a[i,j],s); while length(s)<5 do s:=s+' '; write(s); end; writeln(a[i,m]); end; end.
