Fork me on GitHub

数据结构与算法-搜索(一)-广度优先搜索


数据结构与算法-搜索(一)-广度优先搜索

首先需要说明,这里所说的广度优先搜索,与利用广度优先搜索对图进行遍历有一定的差别。广度优先搜索确实可以以被应用在图的遍历当中,但其应用远不仅如此。我们通过一个例题,引出广度优先搜索:

例:胜利大逃亡

题目描述:

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会,魔王住在一个城堡里,城堡是一个A B C 的立方体,可以被表示成A个B * C 的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个。现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1。

输入:

输入数据的第一行是一个正整数K,表明测试数据的数量。每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1 <= T <= 1000),它们分别代表城堡的大小和魔王回来的时间,然后是A块输入数据(先是第0块,然后是第1块,第2块……),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙。

输出:

对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.

样例输入:

1
2
3
4
5
6
7
8
9
10
11
1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

样例输出:

1
11

代码如下:

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
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

bool mark[50][50][50]; // 标记数组
int maze[50][50][50]; // 保存立方体信息
struct N{ // 状态结构体
int x,y,z;
int t;
};
queue<N> Q; // 队列,队列中的元素为状态
int go[][3] = { // 坐标变换数组,由坐标(x,y,z)扩展得到的新坐标均可通过(x+go[i][0],y+go[i][1],z+go[i][2])得到
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};

int BFS(int a,int b,int c){ // 广度优先搜索,返回其最少耗时
while(Q.empty() == false){ // 当队列中仍有元素可以扩展时循环
N now = Q.front(); // 得到队头状态
Q.pop();
for(int i = 0 ; i < 6 ; i++){
int nx = now.x + go[i][0];
int ny = now.y + go[i][1];
int nz = now.z + go[i][2]; // 计算新坐标
if(nx < 0 || nx >= a || ny < 0 || ny >= b || nz < 0 || nz >= c) continue;
// 若新坐标在立方体外,则丢弃该坐标
if(maze[nx][ny][nz] == 1) continue; // 若该位置为墙,则丢弃该坐标
N tmp; // 新的状态
tmp.x = nx;
tmp.y = ny;
tmp.z = nz;
tmp.t = now.t + 1; // 新状态的耗时
Q.push(tmp); // 将该状态放入队列
mark[nx][ny][nz] = true; // 标记该坐标
if(nx == a-1 && ny == b-1 && nz == c-1) return tmp.t; // 若该坐标即为终点,可直接返回其耗时
}
}
return -1; // 若所有的状态被查找完后,仍得不到所需坐标,则返回-1
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t); // 输入
for(int i = 0 ; i < a ; i++){
for(int j = 0 ; j < b ; j++){
for(int k = 0 ; k < c ; k++){
scanf("%d",&maze[i][j][k]); // 输入立方体信息
mark[i][j][k] = false; // 初始化标记数组
}
}
}
while(Q.empty() == false) Q.pop(); // 清空队列
mark[0][0][0] = true; // 标记起点
N tmp;
tmp.t = tmp.y = tmp.x = tmp.z = 0; // 初始状态
Q.push(tmp); // 将初始状态放入队列
int rec = BFS(a,b,c); // 广度优先搜索
if(rec <= t) printf("%d\n",rec); // 若所需时间符合条件,则输出
else printf("-1\n"); // 否则输出-1
}
return 0;
}

运行结果:

例:非常可乐

题目描述:

大家一定觉得运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝得和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N毫升和M毫升,可乐的体积为S(S < 101)毫升(正好装满一瓶),它们三个之间可以互相倒可乐(都是没有刻意的,且S == N + M,101>S>0,N>0,M>0)。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少次数,如果不能输出”NO”

输入:

三个整数:S 可乐的体积,N和M是两个杯子的容量,以”0 0 0”结束。

输出:

如果能平分的话请输出最少要倒的次数,否则输出”NO”。

样例输入:

1
2
3
7 4 3
4 1 3
0 0 0

样例输出:

1
2
NO
3

代码如下:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct N{ // 状态结构体
int a,b,c; // 每个杯子中可乐的体积
int t; // 得到该体积组倾倒次数
};

queue<N> Q; // 队列
bool mark[101][101][101]; // 对体积组(x,y,z)进行标记,即只有第一次得到包含体积组(x,y,z)的状态为有效状态,其余的舍去

void AtoB(int &a,int sa,int &b,int sb){
// 倾倒函数,由容积为sa的杯子倒往容积为sb的杯子,其中引用参数a和b,初始时为原始杯子中可乐的体积,当函数调用完毕后,为各自杯中可乐的新体积。
if(sb - b >= a){ // 若a可以全部倒到b中
b += a;
a = 0;
}else{
a -= sb - b;
b = sb;
}
}

int BFS(int s,int n,int m){
while(Q.empty() == false){
N now = Q.front();
Q.pop();
int a,b,c;
a = now.a;
b = now.b;
c = now.c;
AtoB(a,s,b,n); // 由a倾倒向b
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
a = now.a;
b = now.b;
c = now.c; // 重置a,b,c为未倾倒前的体积
AtoB(b,n,a,s); // 由b倾倒向a
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
a = now.a;
b = now.b;
c = now.c;
AtoB(a,s,c,m); // 由a倾倒向c
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
a = now.a;
b = now.b;
c = now.c;
AtoB(c,m,a,s); // 由c倾倒向a
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
a = now.a;
b = now.b;
c = now.c;
AtoB(b,n,c,m); // 由b倾倒向c
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
a = now.a;
b = now.b;
c = now.c;
AtoB(c,m,b,n); // 由c倾倒向b
if(mark[a][b][c] == false){
mark[a][b][c] = true; // 标记该体积组
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = now.t+1; // 生成新的状态
if(a == s/2 && b == s/2) return tmp.t;
if(c == s/2 && b == s/2) return tmp.t;
if(a == s/2 && c == s/2) return tmp.t;

Q.push(tmp);
}
}
return -1;
}
int main(){
int s,n,m;
while(scanf("%d%d%d",&s,&n,&m)!=EOF){
if(s == 0) break;
if(s % 2 == 1){ // 若s为奇数则不可能平分,直接输出NO
puts("NO");
continue;
}
for(int i = 0 ; i <= s ; i++){
for(int j = 0 ; j <= n ; j++){
for(int k = 0 ; k <= m ; k++){
mark[i][j][k] = false;
}
}
}// 初始化状态
N tmp;
tmp.a = s;
tmp.b = 0;
tmp.c = 0;
tmp.t = 0;
while(Q.empty() == false) Q.pop(); // 清空队列中的状态
Q.push(tmp); // 将初始状态放入队列
mark[s][0][0] = true; // 标记初始状态
int rec = BFS(s,n,m); // 广度优先搜索
if(rec == -1)
puts("NO");
else printf("%d\n",rec);
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%