洛谷 1443——马的遍历（广度优先搜索）

本文主要是介绍洛谷 1443——马的遍历（广度优先搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有一个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;
beginif (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;
beginfillchar(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;repeatinc(head);for i:=1 to 8 doif pd(state[head,1]+dx[i],state[head,2]+dy[i])=true thenbegininc(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;beginread(n,m,qx,qy);for i:=1 to n dofor j:=1 to m do a[i,j]:=-1;a[qx,qy]:=0;bfs;for i:=1 to n dobeginfor j:=1 to m dobeginstr(a[i,j],s);write(s,' ':5-length(s));end;writeln;end;
end.