所谓双向广度搜索指的是搜索沿两个方向同时进行：（1）正向搜索：从初始结点向目标结点方向搜索；（2）逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。

      广度双向搜索通常有两种方法：（1）两个方向交替扩展；（2）选择结点个数较少的那个方向先扩展。方法（2）克服了两方向结点的生成速度不平衡的状态，可明显提高效率。

【例1】Knight Moves （POJ 1915）

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.

Input

The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.
Output

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.
Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Sample Output

5
28
0

       （1）编程思路1。

       先采用一般的单向广度优先搜索方法。设置数组step[305][305]记录走到某个位置需要的步数，数组vis[305][305]来记录某个位置是否已访问过（值0代表未访问，1代表已访问过）。

       用数组q[]来模拟队列，front和rear分别为队头和队尾指针。单向广度优先搜索的框架可写为：

           队列初始化，即front=rear=0;

           起点坐标入队列;

           while (front<rear)      // 队列不为空

           {

                  队头元素出队，送cur结点；

                  若cur结点的坐标等于终点坐标，则搜索完成，返回；

                  将cur结点按规则展出新结点next（即用循环进行8个方向的新结点生成）；

                     若next结点未访问过，则置相应的值，并将next结点入队；

            }

      （2）采用单向广度优先搜索的源程序。

#include <stdio.h>

int vis[305][305], step[305][305];

int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};

int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

struct point

{

     int x, y;

};

int BFS(int start_x,int start_y,int end_x,int end_y,int n)

// 在n*n的棋盘中搜索从起点（start_x,strat_y)到终点（end_x,end_y)所需的最少步数

{

     int front,rear,i;

     point cur,next,q[90005];

     front=rear=0;

     cur.x = start_x;

     cur.y = start_y;

     vis[start_x][start_y] = 1;   // 设置探索标记为1

     q[rear++] = cur;              // 起始坐标入队

     while (front < rear)

     {

         cur = q[front++];&