广度优先搜索

还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去，但是它不知道到底该怎么走，无论如何还是先选定一个方向走一下再说。我们对各个方向设定一个优先级，比如我们设定先向上走，再向右走，然后是向下，向左。这个顺序是顺时针排的。不难想象，通过设定一个优先级，我们可以保证在行进过程不会因为随机选择而出现重复情况。深度优先搜索的思路是找到一条可能的路就一直那么走下去直到走不通为止。这个走不通可能的情况很多，也许是遇到了自然的障碍物，也许是到了死胡同走不下去了，这个时侯只有倒退回去。但是现实总是充满了陷阱，或许就存在这么一种路，当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以在人生里为我们设定。

第1页/共161页我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢？对，我们可以叫住他！“喂，那条路不能走了，快回来！”实现起来其实很简单，就是在程序里面加一个深度判断，如果深度达到了一个上界，我们就不继续往下走了，也就是跳出返回。其实这里面要涉及的还有很多，比如迭代加深搜索，A*等。其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠，而是一大群，如果你是老鼠王，你会怎么安排让你的子民们尽快逃生？Thinking。。。第2页/共161页很简单，让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队，四个小队分别分别负责四个方向，一起出发。每次只能选择没有去过的地方走，没有去过既包括自己没有去过也要包括别的老鼠没有去过，这个我们可以用一个布尔数组在去过的地方标记一下，对于小老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法，那好，我们把当前的这个小队再次划分，每个能走的方向都派一个小小队去。如果没有路可走了，就呆在那儿了。当有一队老鼠或者是一只找到了出口，这位英雄就在对讲机里大吼一声，“哈哈，我找到出口啦，大家到这里来”。

第3页/共161页相信大家听问题的时候都注意到了关键词“尽快”。毋庸置疑，老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置的距离为0，由这个位置出发能到的距离为1，再有这些点能到的不重复的点的距离为2。。。如此下去，我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了，而且也没有走重复的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。这就是宽度优先搜索。恭喜老鼠们成功获救！可是现在的问题我们如何在程序里面实现？第4页/共161页BFS的关键：队列我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我们来说，只有在知道当前老鼠的位置的前提下，我们才能产生下一时间的决策。而为了达到上面所说的拓展最短，我们就必须根据各个位置被到达的先后顺序来拓展。这就要用到队列。第5页/共161页队列第6页/共161页队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。故队列又称为先进先出（FIFO—firstinfirstout）线性表。第7页/共161页队列可以用数组queue[1…maxn]来存储，数组的上界maxn即是队列所容许的最大容量。在队列的运算中需设两个指针：head，队头指针，指向实际队头元素；tail，队尾指针，指向实际队尾元素的下一个位置。第8页/共161页123Push入队Procedurepush(x:integer);BeginQueue[tail]:=x;tail:=tail+1;End;headtail567840第9页/共161页123Pop出队Procedurepop;Beginwrite(Queue[head]);head:=head+1;End;headtail45678队列为空的标志是head追上tail，即head=tail第10页/共161页队列应用例0：解密QQ。新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问QQ号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数放到这串数的末尾，再将第5个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“631758924”。输入：9631758924输出615947283第11页/共161页分析：首先需要一个数组queue来存储这一串数，并初始化这个数组即(6,3,1,7,5,8,9,2,4)；解密的第一步是将第一个数删除。如何在数组中删除一个数呢？最简单的方法是将所有后面的数都往前面挪动一位，将前面的数覆盖。但是这样的做法很耗费时间。第12页/共161页在这里引入两个整型变量head和tail。head用来记录队列的队首（即第一位），tail用来记录队列的队尾（即最后一位）的下一个位置。你可能会问：为什么tail不直接记录队尾，却要记录队尾的下一个位置呢？这是因为当队列中只剩下一个元素时，队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时，队列为空。第13页/共161页现在有9个数，9个数全部放入队列之后head=1;tail=10;此时head和tail之间的数就是目前队列中“有效”的数。如果要删除一个数的话，将head后移一位就OK了，这样仍然可以保持head和tail之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间，却节省了大量的时间，这是非常划算的。第14页/共161页新增加一个数也很简单，把需要增加的数放到队尾即q[tail]之后再tail后移一位就OK啦。第15页/共161页constmaxn=100;varqueue:array[1..maxn]ofinteger;n,i:integer;head,tail:integer;beginreadln(n);fori:=1tondoread(queue[i]);head:=1;tail:=n+1;//tail指向队尾的后一个位置

whilehead<>taildo//当队列不为空的时候执行循环

begin//打印队首并将队首出队

write(queue[head],'');inc(head);//先将新队首的数添加到队尾

queue[tail]:=queue[head];inc(tail);//再将队首出队

inc(head);end;end.第16页/共161页例1：迷宫问题描述：解救小哈。有一天，小哈一个人去玩迷宫，但是方向感不好的小白就快就迷了路。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫的地图，现在小哼要去解救小哈。问题就此开始了……第17页/共161页任务：帮助小哼找到从迷宫起点通往小哈所在位置的的最少步数，并打印出一条最短路径。输入样例：54001000000010010000011143输出样例：7(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3)第18页/共161页算法分析：最开始小哼在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）12341

■

2

3

■

4

■

5

■

1234第19页/共161页算法分析：最开始小哼在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）12341

■

2

3

■

4

■

5

■

第20页/共161页算法分析：但是小哈并不在这两个点上，那小哼只能通过（1,2）和（2,1）这两个点继续往下走。比如现在小哼走到了（1,2）这个点，之后他又能到达哪些新的点呢？12341

■

2

3

■

4

■

5

■

第21页/共161页算法分析：但是小哈并不在这两个点上，那小哼只能通过（1,2）和（2,1）这两个点继续往下走。比如现在小哼走到了（1,2）这个点，之后他又能到达哪些新的点呢？12341

■

2

3

■

4

■

5

■

第22页/共161页算法分析：再看看通过（2,1）又可以到达哪些点呢？12341

■

2

3

■

4

■

5

■

第23页/共161页算法分析：再看看通过（2,1）又可以到达哪些点呢？12341

■

2

3

■

4

■

5

■

第24页/共161页算法分析：此时，你会发现（2,2）这个点既可以从（1,2）到达，也可以从（2,1）到达，并且都只使用了2步。为避免一个点多次被走到，这里需要一个数组来记录一个点是否已走过。12341

■

2

3

■

4

■

5

■

第25页/共161页算法分析：此时，小哼2步可以走到的点已全部走过，有（2,2)和（3,1），可小哈并不在这两个点上，还得继续往下尝试，看通过（2，2）和（3,1）这两个点还能到达哪些新的没有走过的点。12341

■

2

3

■

4

■

5

■

第26页/共161页算法分析：通过（2,2）我们可以到达（2,3）和（3,2）通过（3,1）我们可以到达（4,1）12341

■

2

3

■

4

■

5

■

第27页/共161页算法分析：搜索继续……12341

■

2

3

■

4

■

5

■

第28页/共161页算法分析：搜索继续……12341

■

2

3

■

4

■

5

■

第29页/共161页算法分析：搜索继续……12341

■

2

3

■

4

■

5

■

第30页/共161页算法分析：当进行到第7步时，终于“抱得美人归”。12341

■

2

3

■

4

■

5

■

第31页/共161页回顾一下刚才的算法，可以用一个队列来模拟整个过程。123456789……xyprestep每个队列元素至少包含下列信息：x:横坐标y:纵坐标pre:由哪一个节点扩展而来（父节点）step:第几步扩展到该节点第32页/共161页算法分析：操作：队列指针初始化；将起点信息入队

12341

■

2

3

■

4

■

5

■

0123456789……xyprestep1234headtail第33页/共161页算法分析：操作：队列指针初始化；将起点信息入队

12341

■

2

3

■

4

■

5

■

0123456789……x1y1pre0step01234headtail第34页/共161页算法分析：操作：检测到队列不为空（head<>tail），则inc(head)

12341

■

2

3

■

4

■

5

■

0123456789……x1y1pre0step0headtail第35页/共161页算法分析：操作：准备扩展高亮显示的节点

12341

■

2

3

■

4

■

5

■

0123456789……x1y1pre0step0headtail1234第36页/共161页算法分析：操作：按顺时针方向搜索可到达的格子，例如（1,2）

12341

■

2

3

■

4

■

5

■

0123456789……x1y1pre0step0headtail1234第37页/共161页算法分析：操作：inc(tail)；将队首节点可到达节点（1,2）入队

12341

■

2

3

■

4

■

5

■

0123456789……x1y1pre0step0headtail1234第38页/共161页

12341

■

2

3

■

4

■

5

■

0123456789……x11y12pre01step01head1234tail第39页/共161页算法分析：操作：继续搜索可到达的格子，例如（2,1）

12341

■

2

3

■

4

■

5

■

0123456789……x11y12pre01step01headtail1234第40页/共161页算法分析：操作：inc(tail)；将队首节点可到达节点（2,1）入队

12341

■

2

3

■

4

■

5

■

0123456789……x11y12pre01step01headtail1234第41页/共161页

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第42页/共161页算法分析：操作：队首节点扩展完毕

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第43页/共161页算法分析：操作：inc(head);准备扩展队首节点

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第44页/共161页

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第45页/共161页算法分析：操作：搜索队首节点可到达的格子

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第46页/共161页算法分析：操作：搜索队首节点可到达的格子

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第47页/共161页算法分析：操作：搜索队首节点可到达的格子（2,2）

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail1234第48页/共161页算法分析：操作：inc(tail)；将队首可到达的节点入队

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail第49页/共161页算法分析：操作：inc(tail)；将队首可到达的节点入队

12341

■

2

3

■

4

■

5

■

0123456789……x112y121pre011step011headtail第50页/共161页算法分析：操作：inc(tail)；将队首可到达的节点（2,2）入队

12341

■

2

3

■

4

■

5

■

0123456789……x1122y1212pre0112step0112headtail第51页/共161页算法分析：操作：队首节点扩展完毕

12341

■

2

3

■

4

■

5

■

0123456789……x1122y1212pre0112step0112headtail第52页/共161页算法分析：操作：inc(head)，准备扩展队首节点

12341

■

2

3

■

4

■

5

■

0123456789……x1122y1212pre0112step0112headtail第53页/共161页算法分析：操作：搜索队首可到达的格子，例如（2,2）（3,1），其中（2,2）已访问

12341

■

2

3

■

4

■

5

■

0123456789……x1122y1212pre0112step0112headtail第54页/共161页算法分析：操作：inc(tail)

12341

■

2

3

■

4

■

5

■

0123456789……x1122y1212pre0112step0112headtail第55页/共161页算法分析：操作：（3,1）入队

12341

■

2

3

■

4

■

5

■

0123456789……x11223y12121pre01123step01122headtail第56页/共161页算法分析：操作：队首扩展完毕

12341

■

2

3

■

4

■

5

■

0123456789……x11223y12121pre01123step01122headtail第57页/共161页算法分析：操作：inc(head)

12341

■

2

3

■

4

■

5

■

0123456789……x11223y12121pre01123step01122headtail第58页/共161页算法分析：操作：搜索可到达的格子，例如（2,3）

12341

■

2

3

■

4

■

5

■

0123456789……x11223y12121pre01123step01122headtail第59页/共161页算法分析：操作：inc(tail);

12341

■

2

3

■

4

■

5

■

0123456789……x11223y12121pre01123step01122headtail第60页/共161页算法分析：操作：入队

12341

■

2

3

■

4

■

5

■

0123456789……x112232y121213pre011234step011223headtail第61页/共161页算法分析：操作：继续搜索可到达的格子

12341

■

2

3

■

4

■

5

■

0123456789……x112232y121213pre011234step011223headtail第62页/共161页算法分析：操作：继续搜索可到达的格子（3,2）

12341

■

2

3

■

4

■

5

■

0123456789……x112232y121213pre011234step011223headtail第63页/共161页算法分析：操作：inc(tail)

12341

■

2

3

■

4

■

5

■

0123456789……x112232y121213pre011234step011223headtail第64页/共161页算法分析：操作：入队

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第65页/共161页算法分析：操作：队首节点扩展完毕

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第66页/共161页算法分析：操作：inc(head)

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第67页/共161页算法分析：操作：搜索可到达的格子

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第68页/共161页算法分析：操作：搜索可到达的格子

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第69页/共161页算法分析：操作：inc(tail)

12341

■

2

3

■

4

■

5

■

0123456789……x1122323y1212132pre0112344step0112233headtail第70页/共161页算法分析：操作：入队

12341

■

2

3

■

4

■

5

■

0123456789……x11223234y12121321pre01123443step01122333headtail第71页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x11223234y12121321pre01123443step01122333headtail第72页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x11223234y12121321pre01123443step01122333headtail第73页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x11223234y12121321pre01123443step01122333headtail第74页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第75页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第76页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第77页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第78页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第79页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789……x112232342y121213214pre011234436step011223334headtail第80页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x1122323425y1212132141pre0112344368step0112233344headtail第81页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x1122323425y1212132141pre0112344368step0112233344headtail第82页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x1122323425y1212132141pre0112344368step0112233344headtail第83页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x11223234253y12121321414pre01123443689step01122333445headtail第84页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x11223234253y12121321414pre01123443689step01122333445headtail第85页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

01234567891011…x11223234253y12121321414pre01123443689step01122333445headtail第86页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112…x112232342531y121213214144pre011234436899step011223334455headtail第87页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112…x112232342531y121213214144pre011234436899step011223334455headtail第88页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112…x112232342531y121213214144pre011234436899step011223334455headtail第89页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

012345678910111213…x112232342531y121213214144pre011234436899step011223334455headtail第90页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第91页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第92页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第93页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第94页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第95页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第96页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第97页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第98页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第99页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第100页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第101页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第102页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第103页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第104页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第105页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第106页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第107页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第108页/共161页算法分析：操作：……

12341

■

2

3

■

4

■

5

■

0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第109页/共161页广度优先搜索（BreadthFirstSearch,BFS）主要思想：层层递进首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。第110页/共161页BFS代码框架Procedurebfs;Begin

//队列初始化

head:=0;tail:=1;初始状态入队

//当队列不为空的时候执行下列循环（head<>tail）whilehead<>taildobegininc(head);//队首指针+1，指向待扩展节点

fork:=1to算符数dobeginif新节点符合条件thenbegininc(tail);将新节点入队end;if新节点到达目标节点，则停止扩展，输出并退出end;end;End;第111页/共161页广度优先就是走到一个点，将该点周围可走的点走完，然后再按同样规则走其他的点。（大家可以想像一下铺满的多米诺骨牌，将其中一块推倒其余周围的骨牌也会一层层扩散式的倒塌）所以先规定好一个走路的规则，同样按照右下左上顺时针的方式去尝试。如上图僵尸的位置是起始点，先往右走，但是有堵墙走不了，所以按照规定尝试往下走。到达“1”的位置，在“1”处可以知道四周能走的点只有“2”。“2”能走的点有“3”，“4”。来到“3”，发现没有可走的。来到“4”发现去可以去“5”。这样依次进行下去就完成了广度优先搜索。/a396901990/article/details/45028741第112页/共161页constmaxn=20;varn,m,i,j:integer;startx,starty,endx,endy:integer;map:array[1..maxn,1..maxn]ofinteger;used:array[1..maxn,1..maxn]ofboolean;dir:array[1..4,1..2]ofinteger=((0,1),(1,0),(0,-1),(-1,0));queue:array[1..maxn*maxn]ofrecord//队列扩展最大为地图大小

x:integer;//横坐标

y:integer;//纵坐标

pre:integer;//父亲在队列中的编号

step:integer;//步数

end;head,tail:integer;flag:boolean;第113页/共161页procedurebfs;vark:integer;nx,ny:integer;begin//队列初始化

head:=0;tail:=1;//往队列插入迷宫入口坐标

queue[tail].x:=startx;queue[tail].y:=starty;queue[tail].pre:=0;queue[tail].step:=0;used[startx,starty]:=true;第114页/共161页flag:=false;//标记是否到达目标点

//当队列不为空的时候循环（head=tail）

whilehead<>taildobegininc(head);fork:=1to4dobeginnx:=queue[head].x+dir[k,1];ny:=queue[head].y+dir[k,2];if(nx<=0)or(nx>n)or(ny<=0)or(ny>m)thencontinue;if(map[nx,ny]=0)and(used[nx,ny]=false)thenbegin//标记(nx,ny)已走过

//将点（nx,ny）入队，注意宽搜每个点只入队一次，与深搜

//不同，不需要将used数组还原

inc(tail);queue[tail].x:=nx;queue[tail].y:=ny;queue[tail].pre:=head;//记录点(nx,ny)的父节点编号headqueue[tail].step:=queue[head].step+1;//步数是到达父节点步数+1used[nx,ny]:=true;end;