洛谷 P1443 马的遍历

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

一行四个数据，棋盘的大小和马的坐标

输出格式：

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例

输入样例#1： 3 3 1 1 输出样例#1： 0 3 2 3 -1 1 2 1 4 const dx:array[1..8] of longint=(2,1,-1,-2,-2,-1,2,1); dy:array[1..8] of longint=(-1,-2,-2,-1,1,2,1,2); var s:array[1..1000,1..1000] of longint; a:array[1..10000,1..2] of longint; bz:array[1..1000,1..1000] of boolean; n,m,x,y,i,j,p:longint; procedure aa(c,d:longint)； var i,j,k,teal,word,x,y:longint; begin bz[c,d]:=false; teal:=1; word:=1; a[t,1]:=c; a[t,2]:=d; s[c,d]:=1; repeat for i:=1 to 8 do begin x:=a[teal,1]+dx[i]; y:=a[t,2]+dy[i]; if (x>0)and(x<=n)and(y>0)and(y<=m)and bz[x,y] then begin inc(word); a[word,1]:=x; a[word,2]:=y; bz[x,y]:=false; s[x,y]:=s[a[teal,1],a[teal,2]]+1; end; end; inc(teal); until teal>word; end; begin readln(n,m,x,y); fillchar(s,sizeof(s),0); fillchar(bz,sizeof(bz),true); aa(x,y); for i:=1 to n do begin for j:=1 to m do begin write(s[i,j]-1); if (s[i,j]-1<10)and(s[i,j]-1>=0)then write(' '); if ((s[i,j]-1<100)and(s[i,j]-1>=10))or(s[i,j]-1=-1) then write(' '); if (s[i,j]-1<1000)and(s[i,j]-1>=100) then write(' '); if s[i,j]-1>=1000 then write(' '); end; writeln; end; end.