队列（queue）只允许从队尾入队、从队头出队，不允许在中间位置插入和删除，不支持数组表示法和随机访问。使用queue时需要引入头文件#include<queue>。队列的基本操作很简单，包括入队、出队、取队头、判断队空、求队列大小。

● queue<int> q ：创建一个空队 q ，数据类型为int。

● push( x )： x 入队。

● pop()：出队。

● front()：取队头（未出队）。

● empty()：判断队列是否为空，若为空，则返回true。

● size()：求队列大小，返回队列中的元素个数。

训练　骑士移动

题目描述（POJ1915）： 写程序，计算骑士从一个位置移动到另一个位置所需的最少移动次数。骑士移动的规则如下图所示。

输入： 输入的第1行为测试用例的个数 N 。每个测试用例都包含3行。第1行表示棋盘的长度 L （4≤ L ≤300），棋盘的大小为 L × L ；第2行和第3行包含一对{0,…, L -1}×{0,…, L -1}的整数，表示骑士在棋盘上的起始位置和结束位置。假设这些位置是该棋盘上的有效位置。

输出： 对于每个测试用例，都单行输出骑士从起点移动到终点所需的最少移动次数。如果起点和终点相等，则移动次数为零。

1. 算法设计

本题是求解棋盘上从起点到终点最短距离的问题，可以使用queue进行广度优先搜索，步骤如下：

（1）如果起点正好等于终点，则返回0；

（2）将起点放入队列；

（3）如果队列不空，则队头出队，否则扩展8个方向，如果找到目标，则立即返回步长+1，否则判断是否越界；如果没有越界，则将步长+1并放入队列，标记其已访问。如果骑士的当前位置为( x , y )，则移动时当前位置坐标加上偏移量即可。例如骑士从当前位置移动到右上角的位置( x -2, y +1)，如下图所示。

8个方向的位置偏移如下。

也可以用一个二维数组int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1}表示位置偏移。 UZ+iIA3HxXph0g5ma4pXEyhfcb39H/+ifTIfT/7739RlQRGXk9wRBtdRNl8Ha77h

2. 算法实现