题解 P1443 【马的遍历】
这里给大家小小的普及一下广搜。（建议先掌握深搜）个人觉得luogu里这题可以用来入门。
深搜与广搜的搜索模式
首先，我们就这道题而言，深搜的话，应该是这样：
尝试8个方向的一个->尝试新坐标8个方向的一个->…………->返回尝试下一个方向……
也就是说，作为一棵树，我们先尝试一个分支，没分支了再返回寻找下一个分支继续。于是可以用来穷举所以情况。
这里吐槽一句，我第一次不知不觉写成深搜了。。。ovo。
但是广搜我们知道它可以用来找到最小路径。。我们看一下它的搜索过程：
尝试8个方向的一个->尝试8个方向的另一个……尝试完所有八个方向，从新的八个坐标开始……搜索到结果，结束。
也就是说，作为一棵树，我们先尝试完所有第一层，第二层，知道找到答案为止，这样可以找到最短路径，为什么呢，假设这个马走到X,Y要跳3步，我们先尝试了所有走零步，一步，两步的情况，所以在第三步的情况搜索到的就是最优答案。
广搜的代码模式
我讲的不是很清楚，上面建议先看过其他广搜材料的再看看。
现在讲一下广搜的代码模式
首先说明，尽管广搜概念上看起来很像需要递归，但实际上这样应该是写不出来的，或者写着写着就写成深搜了。。
因为实际上广搜是靠队列进行的个人概念弄懂后代码还是一脸懵比，所以来讲一下这个代码模式，希望对大家有帮助。
首先，我们需要一个队列，其实就是一个数组。还需要两个变量，就b,t吧，代表队列头和队列尾。
我们把马看做一个点，有八个方向可以走，我们就扩展八个节点，同时用一个while循环来控制搜索，条件b<=t,意思是队列不是空的时候进行。
什么叫队列不为空呢？其实在搜索过程中，我们会不断扩展队列尾，但是队列头用过之后我们就会+1，这样当所有节点扩展完后，队列搜完就是全部搜完了。其实就是把要搜索的节点全找出来，同时一个一个搜过去。
之后扩展节点并且加入队列，就完成了。
注意
1.队列要开大一点
2.需要有一个结构，分别是x，y和步数
3.由于广搜不需要回溯，故要有一个数组标记已走过的点
代码
type
dl=record
x,y,bs:longint;//x,y,step
end;
var sc,bz:array[1..1000,1..1000]of longint;//输出，标志
cd:array[1..50000]of dl;//队列
fx:array[1..8,1..2]of longint=((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2));//八个方位
n,m,i,j,qx,qy:longint;//棋盘长，宽，计数ij，起点坐标
te:ansistring;
procedure search(x,y:longint);
var hx,hy:longint;//变化后x,y
b,e,k:longint;//begin,end,计数
begin
b:=1;e:=1;
cd[1].bs:=0;
cd[1].x:=x;
cd[1].y:=y;
while(b<=e)do begin
for k:=1 to 8 do begin
hx:=cd[b].x+fx[k][1];
hy:=cd[b].y+fx[k][2];
if(hx>=1)and(hx<=n)and(hy>=1)and(hy<=m)and(bz[hx,hy]=0)then begin
inc(e);
bz[hx,hy]:=1;
cd[e].x:=hx;
cd[e].y:=hy;
cd[e].bs:=cd[b].bs+1;
sc[hx,hy]:=cd[e].bs;
end;
end;
inc(b);
end;
exit;
end;
begin
readln(n,m,qx,qy);
fillchar(bz,sizeof(bz),0);
search(qx,qy);
for i:=1 to n do begin
for j:=1 to m do begin
if(sc[i,j]=0)then
sc[i,j]:=-1;
end;
sc[qx,qy]:=0;
end;
for i:=1 to n do begin
for j:=1 to m do begin
str(sc[i,j],te); //感谢 @hz1624917200 的输出优化方案
write(te,'':5-length(te));
end;
writeln;
end;
readln;readln;
end.