题目描述
有一个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这题bfs学的好的人完全不是问题,用头指针head和尾指针tail来记录当前搜到那个点head,将这个点存在tail的位置。
向八个方向搜,如果这个点没有被搜过(广搜如果搜到一定是最优解)和没有跳出范围。就将这个点存起来,最后输出最坑,要将长度补齐,不能只输出一个空格。代码如下:
const dx:array[1..8]of longint=(1,1,-1,-1,2,2,-2,-2); dy:array[1..8]of longint=(2,-2,2,-2,1,-1,-1,1);var n,m,qx,qy,i,j:longint; s:string; a:array[-10..502,-10..502]of longint; f:array[-10..502,-10..502]of boolean;function pd(x,y:longint):boolean;begin if (x<1)or(y<1)or(x>n)or(y>m) then exit(false); if f[x,y]=false then exit(false); exit(true);end;procedure bfs;var head,tail,i:longint; state:array[0..160001,1..2]of longint; father:array[0..160001]of longint;begin fillchar(state,sizeof(state),#0); fillchar(father,sizeof(father),#0); head:=0; state[1,1]:=qx; state[1,2]:=qy; tail:=1; father[1]:=0; fillchar(f,sizeof(f),true); f[qx,qy]:=false; repeat inc(head); for i:=1 to 8 do if pd(state[head,1]+dx[i],state[head,2]+dy[i])=true then begin inc(tail); state[tail,1]:=state[head,1]+dx[i]; state[tail,2]:=state[head,2]+dy[i]; father[tail]:=father[head]+1; a[state[tail,1],state[tail,2]]:=father[tail]; f[state[tail,1],state[tail,2]]:=false; end; until head>=tail;end;begin read(n,m,qx,qy); for i:=1 to n do for j:=1 to m do a[i,j]:=-1; a[qx,qy]:=0; bfs; for i:=1 to n do begin for j:=1 to m do begin str(a[i,j],s); write(s,' ':5-length(s)); end; writeln; end;end.