STL应用 —— queue(队列)

STL应用 —— queue(队列)

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

• queueq：创建一个空队，数据类型为int
• push(x)：x入队
• pop()：出队
• front()：取队头(不出队)
• empty()：判断队列是否为空，若为空，返回true
• size()：求队列大小，返回队列中的元素个数。

举个栗子

POJ No. 1915

官方题目地址

题意：

编写程序，计算骑士从一个位置移动到另一个位置所需的最少移动次数。

移动规则：

样例：

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

输出：

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

算法设计

→ 使用queue进行广度优先搜索。

步骤：

• 如果起点正好等于终点，返回0
• 将起点放入队列
• 如果队列不空，则队头出队，否则扩展8个方向，如果找到目标，则立即返回步长 + 1，否则判断是否越界；如果没有越界，则将步长 + 1放入队列，标记其已访问。如果当前骑士的位置是(x , y)，则移动时当前位置坐标加上偏移量即可。

8个方向的位置偏移：

int dx[8] = {-2 , -2 , -1, -1 , 1, 1 , 2, 2};  //行偏移量
int dy[8] = {1 ,  -1,   2 ,-2 , 2 ,-2 ,1,-1};  //列偏移量

//也可以用一个二维数组
int dir[8][2] = {-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1} 表示位置偏移
1
2
3
4
5

算法实现

#include
#include
#include
#include
#include

const int maxN = 310;

using namespace std;

struct point{ //到达的点和需要的步数 
	int x , y;
	int step;
};

int dx[8] = {-2,-2,-1,-1,1,1,2,2}; //行偏移量 
int dy[8] = {1,-1,2,-2,2,-2,1,-1}; //列偏移量

bool visited[maxN][maxN];

int sx , sy , ex , ey ,tx , ty ,L;

int bfs(){
	
	if(sx == ex && sy == ey){
		return 0;
	}
	
	memset(visited , false , sizeof(visited)); //初始化是否已访问数组
	
	queue<point>Q;
	
	point start , node;
	
	start.x = sx;
	
	start.y = sy;
	
	start.step = 0;  //队列初始化
	
	Q.push(start); //压入队列
	
	int step , x , y;
	
	while(! Q.empty()){
		start = Q.front() , Q.pop(); //取队列头元素，同时把这个元素弹出
		x = start.x;
		y = start.y;
		
		step = start.step; //将队列头元素的x ， y ， step取出
		
		for(int i = 0 ; i < 8 ; i ++){
			tx = x + dx[i];
			ty = y + dy[i];
			
			if(tx == ex && ty == ey){
				return step + 1;
			}
			if(tx >= 0 && tx < L && ty >= 0 && ty < L && !visited[tx][ty]){
				node.x = tx;
				node.y = ty;
				
				node.step = step + 1;
				Q.push(node); //满足条件的进队 
				visited[tx][ty] = true;
			}
		} 
		
	} 
}


int main(){
	
	int N;
	scanf("%d" , &N);
	
	while(N --){
		scanf("%d" , &L);
		scanf("%d%d",&sx , &sy);
		scanf("%d%d",&ex,&ey);
		printf("%d\n",bfs());
	}
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

运行结果