前言：

​ 本篇文章是对我学习广度优先时所刷部分题目的总结。

什么是广度优先搜索

​ 我理解的广度优先搜索是在横向进行搜索的时候使用的方法。具体说明参照百度百科就好了。

算法应用场景

​ 最简单明了的需要用到广度优先的题目一般是让你在一个图上找到从某点到另外一点最短的距离。这样的题目出来了就是用广度优先，虽然有时候深度优先也可以但是一般广度优先会更好。

​ 广度优先搜索的题目意思都是 说从某点开始以特定的步骤进行移动最终到达符合条件的点。这里并不仅仅局限于图论，还可以用于其他的地方。

​ 总而言之，凡是需要进行横向查询某一个事物的时候都可以使用广度优先搜索。

具体题目

这里我展示一些经典的题目来具体说明。

POJ 3699

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
Description

Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti  ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

Input

* Line 1: A single integer: M
* Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti

Output

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5
Sample Output

5
Source

USACO 2008 February Silver

中文翻译（来自有道）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
描述

贝茜听说一场非凡的流星雨要来了;报道称，这些流星会撞向地球，并摧毁它们击中的任何东西。由于担心自己的安全，她发誓要找到一个安全的地方(一个不会被流星摧毁的地方)。她目前正在坐标平面的原点觅食，想要移动到一个新的、更安全的位置，同时避免被沿途的流星摧毁。

报道称将有M颗流星(1≤M≤50,000颗)撞击，流星i将撞击点(Xi, Yi)(0≤Xi≤300;0≤Yi≤300)，Ti(0≤Ti≤1000)。每颗流星都会破坏它撞击的点以及四个直线相邻的格点。

贝茜在时间0离开原点，可以在第一象限以每秒一单位的速度平行于坐标轴，移动到任何尚未被流星摧毁的相邻直线点。她不可能在任何时间被定位在一个点上，大于或等于它被摧毁的时间)。

确定贝西到达安全地点的最短时间。

输入
*第1行:单个整数:M
*线2 . .M+1:第i+1行包含三个用空格分隔的整数:Xi, Yi, Ti
输出
*第一条:贝西到达安全地点的最短时间，如果不可能，最短时间为-1。

分析：

​ 这明显符合我们说的从某点开始然后以特定的步骤进行移动最终到达符合条件的点。那么要描述贝茜位置和被流星砸到的位置那么我们可以用图这个数据结构来表述。图中的每一个（x，y）点存它被砸到的时间。至于贝茜所在的位置我们可以用额外的变量x，y来存放。我们也要用一个时间变量t来存当贝茜来到（x，y）所对应的时间。我为了更方便一些（对我而言）所以我将贝茜所属的x，y，t用一个自定义的结构体来表述。

1
2
3
4
struct Node
{
	int x, y, t;//贝茜所属的时间变量t和所在位置（x,y）
};

​ 因为题目中Ti最大为1000所以我们可以设INF=1001表示这个点是安全点。每次流星砸下时都会影响其周围4个方位的点（上下左右4个方位）。这时候就会出现一个这样的情况：点（1，2）将在3秒钟的时候被流星砸到，但是点（1,1）可能在3秒前就被砸了。这就意味着点（1,2）在3秒前就不是安全点了，也就是说图中这个点存的时间不应该是3而是(1,1)被砸的时间。所以每次得到一组流星下落的数据时，图中每点存的应该是最小的不安全时间。题目中说贝茜在时间0离开原点，从这句中我们可以知道贝茜初始的x=y=t=0。所以如果在时间为0时就有一个流星砸落那么贝茜就会直接死去这就意味着她不存在安全点直接就可以输出-1。题目还有一个要在意的点就是题目中的图应该是无穷大的（即x和y都是大于等于0）。不过题目中限定了x和y都在0到300之间。但是我们要知道贝茜是可以到这些点之外的，而这些之外的点必是安全点。

​ 对于题目的分析就在上面这两段了。那么接下来我就来说明如何使用广度优先搜索来解题。

​ 广度优先搜索就是一开始就举出所有贝茜可以到达的点（即此点是安全点或者此点的被摧毁时间t1应该小于贝茜通过之前的点到达此点的时间t）。贝茜只能从4个方向进行移动，那我们就将4个方向的结果全部都列出来。其中我们要排除掉不符合规则的点（x和y小于0的点和被摧毁点）。

​ 贝茜什么时候到一个点时所耗的时间是最少的呢？这应该是贝茜第一次到达这个点，并且之前所在的位置所花费的时间是最小的时候。因为任何的返回都会增加时间，而你可以通过返回到某个点unknow而到达这个点。这就意味着你原本在unknow这个点的时候就可以达到了。所以第一次到达某个点时耗费的时间是最短的。为了防止贝茜进行返回而多增加时间。我们可以设置一个变量来存贝茜已经到达过的点。这时候不符合规则的点又多了一个即已访问点。判断的代码如下：

1
2
3
4
5
6
7
8
int d[][2] = { 1,0,0,1,-1,0,0,-1 };
for (int i = 0; i < 4; i++)
{
	int x = t.x + d[i][0];
	int y = t.y + d[i][1];
	if (x >= 0 && y >= 0 && a[x][y] > t.t + 1&&v[x][y]==0){}
	//a存储被摧毁的时间。v存是否被访问，被访问设1否则为0。
}

​ 如何存储每次判断后符合条件的点呢？其实只要是可以存储数据的数据结构都可以。但是我们要的这个数据结构应该要把我们的数据按照时间从小到大排列好。只有按照这个规则排列我们才会第一次到即是得到最小时间。我们一开始从（0，0）点开始移动的时候所到的4个位置（其实只有两个）必然是耗最小的时间到达。这是因为（0，0）点时贝茜必然是所耗时间最少的，那她所能到达她周围的点也是时间最少的。但是我们要想到一个情况即会不会出现一个点（x1，y1）到（x1，y1-1）的时间会高于从（x1-1，y1-1）的时间呢（这里设贝茜到（x1，y1）与（x1-1，y1-1）都是其图中最小时间）。面对这样的问题我们只要让（x1-1，y1-1）比（x1，y1）早一步进行判断并且将（x1,y1-1）设为已访问就可以了。所以我们每次才要从时间最小开始判断。当然你可以用一个数组加上sort函数进行排列。不过其实我们只要用一个队列就解决了。至于为什么用队列你可以想一下（感觉我文字写太多了怕你们头疼就不多写了，其实也就是队列的特性啦）

通过代码如下：

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
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MMAX = 10000;//表示安全点
struct Node
{
	int x, y, t;//贝茜所属的时间变量t和所在位置（x,y）
};
int a[302][302];//存被摧毁的最小时间
int v[302][302];//用来判断是否被访问，已访问为1否则为0。
int d[][2] = { 1,0,0,1,-1,0,0,-1 };//用来表示贝茜的移动
int bfs()
{
	queue<Node> q;//队列进行存储贝茜的移动。
	Node tmp;
	tmp.x = tmp.y = tmp.t = 0;
	q.push(tmp);
	while (!q.empty())
	{
		Node t = q.front();
		q.pop();
		if (a[t.x][t.y] == MMAX)//判断是否为安全点
			return t.t;//是就直接退出返回到这个点所耗费的时间，因为这时候必然是最小的时间到达。比它时间低的位置已经全部排除。
		for (int i = 0; i < 4; i++)//广度优先判断
		{
			int x = t.x + d[i][0];
			int y = t.y + d[i][1];
			if (x >= 0 && y >= 0 && a[x][y] > t.t + 1&&v[x][y]==0)
			{
				Node t1;
				t1.x = x;
				t1.y = y;
				t1.t = t.t + 1;
				v[x][y] = 1;
				q.push(t1);
			}
		}
	}
	return -1;
}
int main()
{
	int m, x, y, t;
	while (cin>>m)
	{
		//memset(a, 10000, sizeof(a));
		memset(v, 0, sizeof(v));
		for (int i = 0; i < 302; i++)
		{
			for (int j = 0; j < 302; j++)
			{
				a[i][j] = MMAX;//初始化全部设为不能到达
			}
		}
		for (int i = 0; i < m; i++)
		{
			cin >> x >> y >> t;
			a[x][y] = min(a[x][y], t);
			for (int i = 0; i < 4; i++)//每次都要判断一下是否为最小摧毁时间
			{
				int x1 = x + d[i][0];
				int y1 = y + d[i][1];
				if (x1 >= 0 && y1 >= 0)
				{
					a[x1][y1] = min(a[x1][y1], t);
				}
			}
		}
		if (a[0][0] == 0)//如果还没有移动就被砸了，那就必然逃不了
			cout << "-1" << endl;
		else
			cout << bfs() << endl;
	}
	return 0;
}

POJ 3228

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K
Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input

5 17
Sample Output

4
Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

中文翻译（来自有道）

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
描述

农夫约翰被告知有一头逃亡的母牛在哪里，他想立即抓住它。它从数轴上的N(0≤N≤100,000)点开始，而奶牛在同一数轴上的K(0≤K≤100,000)点。农夫约翰有两种交通方式:步行和远距离传送。

*行走:FJ可以在一分钟内从任意点X移动到点X - 1或X + 1

*传送:FJ可以在一分钟内从任意X点移动到2 * X点。

如果奶牛没有意识到它在追赶，完全不动，那么农场主约翰需要多长时间才能把它找回来?

输入

第1行:两个用空格分隔的整数:N和K

输出

第1行:最短的时间，以分钟为单位，农民约翰抓住了逃亡的牛。

样例输入

5 17

样例输出

4

提示

农民约翰到达这头逃亡的母牛的最快的方法是沿着下面的路径走:5-10-9-18-17，这需要4分钟。

分析：

​ 这题很明显符合我上文的描述：求最短，并且横向搜索。看完题目我们可以知道农夫一共有3种移动方式—— 1.x-1，2.x+1，3.2*x。则我们进行bfs的时候就只要判断这三种方向就好了（记得要防止重复走路）。（再多就不说了。如果你还是不会可以去再看看我上题的分析。）

ac代码

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
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int a[100005];
struct Node
{
	int pos, cot;//pos表示现在农夫所在的位置，cot表示农夫在这个位置时所用的时间。
};
int BFS(int n, int k)
{
	queue<Node> q;
	Node node;
	node.pos = n;
	node.cot = 0;
	q.push(node);
	a[n] = 1;
	while (!q.empty())
	{
		Node tmp = q.front();
		q.pop();
		if (tmp.pos == k)//当农夫与奶牛在同一个位置的时候，奶牛就被农夫抓回去了。
			return tmp.cot;
		if (tmp.pos - 1 >= 0&&a[tmp.pos-1]==0)//进行判断防止下溢和农夫回去。
		{
			Node t;
			t.pos = tmp.pos - 1;
			t.cot = tmp.cot + 1;
			a[tmp.pos - 1] = 1;
			q.push(t);
		}
		if (tmp.pos + 1 <= 100000 && a[tmp.pos+1] == 0)//进行判断防止上溢和农夫回去。
		{
			Node t;
			t.pos = tmp.pos + 1;
			t.cot = tmp.cot + 1;
			a[tmp.pos + 1] = 1;
			q.push(t);
		}
		if (tmp.pos*2 <= 100000 && a[tmp.pos*2] == 0)
		{
			Node t;
			t.pos = tmp.pos * 2;
			t.cot = tmp.cot + 1;
			a[tmp.pos * 2] = 1;
			q.push(t);
		}
	}
	return -1;//其实这个毫无意义。因为农夫必抓到奶牛，所以你不加也行。
}
int main()
{
	int n, k;
	cin >> n >> k;
	memset(a, 0, sizeof(a));//这个也可以不加，全局本来就补0了。不过我不知道为什么我不加出错了。
	cout << BFS(n, k) << endl;
	return 0;
}

POJ 2251

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
Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. 

Is an escape possible? If yes, how long will it take? 
Input

The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). 
L is the number of levels making up the dungeon. 
R and C are the number of rows and columns making up the plan of each level. 
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form 
Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape. 
If it is not possible to escape, print the line 
Trapped!
Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 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
描述

你被困在一个3D地牢里，需要找到最快的出路!地下城是由单位立方体组成的，这些立方体可能被石头填充，也可能不被石头填充。它需要一分钟来移动一个单位，北，南，东，西，上或下。你不能沿对角线移动，迷宫四周都是坚硬的岩石。

有可能逃脱吗?如果可以，需要多长时间?

输入



输入由许多地牢组成。每个地下城的描述以一行包含三个整数L, R和C开始(所有的大小限制为30)。

L是组成地下城的关卡数。

R和C是构成每层平面图的行数和列数。

然后会有L个R行块，每个包含C个字符。每个角色描述地牢的一个牢房。充满岩石的单元格用“#”表示，空单元格用“。”表示。你的起始位置用“S”表示，退出位置用“E”表示。每个级别之后都有一个空行。L、R和C的输入以3个零结束。

输出



每个迷宫产生一行输出。如果有可能到达退出，打印表单的一行

在x分钟内逃走。



x被替换为它逃跑所花费的最短时间。

如果无法转义，则打印该行

被困!

样例输入



3 4 5

S . . . .

# # # . .

. # # . .

# # # # .



# # # # #

# # # # #

# # # # .

# # . . .



# # # # #

# # # # #

# # # # .

# # # # E



1 3 3

S # #

# E #

# # #



0 0 0

分析：

​ 其实这还是上面一样的做法。区别在于图的建立。因为这已经不是一个二维的图了，所以我们要加上一个 z 也就是说我们要用三维数组来存这个图。然后接下来就是挨个判断然后防止回去等（套路一样了）。要注意的是当遇到l=r=c=0的时候就结束输入了（没看到这个我wa好多次 (ノへ￣、)）。

ac代码

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
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
	int x, y, z, c;
};
int solve(int l,int r,int c)
{
	int a[2][3][3] = { -1,0,0,1,0,0,0,-1,0,0,1,0,0,0,-1,0,0,1 };//用数组的方式进行点的移动，否则判断要写6个容易错。至于我为什么会知道。。。
	char g[35][35][35];//存图
	int v[35][35][35];//记录此点是否被访问
	queue<Node> q;
	Node b;//存S点
	for (int i = 0; i < l; i++)
	{
		for (int j = 0; j < r; j++)
		{
			for (int h = 0; h < c; h++)
			{
				cin >> g[i][j][h];
				v[i][j][h] = 0;//输入时顺便初始化一下，当然你也可用用memset(v,0,sizeof(v))来初始化。
				if (g[i][j][h] == 'S')//找到开始的点
				{
					b.x = j;
					b.y = h;
					b.z = i;
					b.c = 0;
					q.push(b);//加入队列
				}
				if (g[i][j][h] == '#')//'#'表示的是石头，你不可到达所以那就直接让这点的v为1。
					v[i][j][h] = 1;
			}
		}
	}
	while (!q.empty())
	{
		Node t = q.front();
		q.pop();
		if (g[t.z][t.x][t.y] == 'E')//到了出口直接输出就好了
		{
			printf("Escaped in %d minute(s).\n", t.c);//建议用printf()因为不容易出错。
			return 0;//找到了就直接退出函数了。
		}
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				Node tmp;
				tmp.x = t.x + a[i][j][0];//移动到新点
				tmp.y = t.y + a[i][j][1];
				tmp.z = t.z + a[i][j][2];
				tmp.c = t.c + 1;
				if (tmp.x >= 0 && tmp.x < r && tmp.y < c && tmp.y >= 0 
					&& tmp.z >= 0 && tmp.z < l && v[tmp.z][tmp.x][tmp.y] == 0)//进行个点值上溢、下溢和是否被访问的判断
				{
					v[tmp.z][tmp.x][tmp.y] = 1;//表示此点已被访问。
					q.push(tmp);//加入队列。
				}
			}
		}
	}
	cout << "Trapped!" << endl;//while循环结束后没有退出函数就意味着不可达。所以在这放个输出
	return 0;
}
int main()
{
	int l, r, c;
	while (cin >> l >> r >> c && l != 0 && r != 0 && c != 0)//循环输入并判断l，r，c的值是否合法。
	{
		solve(l, r, c);
	}
	return 0;
}

​ 当然这题对于E点的判断可以放在判断是否被访问的时候进行。因为S点和E点是不可能重合的（毕竟他们要用不同的两个字母表达）。所以你可以直接放的。这样程序会快上16ms（这是我两次提交的结果）。

Aizu 0121

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
7 パズル
7 パズルは 8 つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれのカードには、互いに区別できるように 0, 1, 2, ..., 7 と番号がつけられています。枠には、縦に 2 個、横に 4 個のカードを並べることができます。

7 パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで 0 のカードだけは、上下左右に隣接するカードと位置を交換することができます。たとえば、枠の状態が図(a) のときに、0 のカードの右に隣接した、7 のカードと位置を交換すれば、図(b) の状態になります。あるいは、図(a) の状態から 0 のカードの下に隣接した 2 のカードと位置を交換すれば図(c) の状態になります。図(a) の状態で 0 のカードと上下左右に隣接するカードは 7 と 2 のカードだけなので、これ以外の位置の入れ替えは許されません。

ゲームの目的は、カードをきれいに整列して図(d) の状態にすることです。最初の状態を入力とし、カードをきれいに整列するまでに、必要な最小手数を出力するプログラムを作成してください。ただし、入力されたカードの状態からは図(d) の状態に移ることは可能であるとします。

入力データは、1 行に 8 つの数字が空白区切りで与えられます。これらは、最初の状態のカードの並びを表します。例えば、図(a) の数字表現は0 7 3 4 2 5 1 6 に、図(c) は 2 7 3 4 0 5 1 6 となります。

	
図(a) 0 7 3 4 2 5 1 6 の場合	図(b) 7 0 3 4 2 5 1 6 の場合


	
図(c) 2 7 3 4 0 5 1 6 の場合	図(d) 0 1 2 3 4 5 6 7 (最終状態)

Input
上記形式で複数のパズルが与えられます。入力の最後まで処理してください。 与えられるパズルの数は 1,000 以下です。

Output
各パズルについて、最終状態へ移行する最小手数を１行に出力してください。

Sample Input
0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0
Output for the Sample Input
0
1
28
Source: https://onlinejudge.u-aizu.ac.jp/problems/0121

翻译（来自有道）

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
7智力游戏

7智力游戏由8个正方形的卡和这些卡紧紧相扣的框构成。每个卡片上都有0、1、2、…，号码是7。框可以竖着摆2个，横着摆4个卡片。

7开始解谜的时候，首先将所有的卡放入框中。在框中只有0的卡，可以和上下左右相邻的卡交换位置。例如，框的状态是图(a)的时候，与0的卡的右边邻接的，7的卡交换位置的话，图(b)的状态。或者，从图(a)的状态到图(c)的状态与相邻的2的卡交换位置。图(a)的状态下0的卡和上下左右相邻的卡只有7和2卡，除此以外的位置不允许调换。

游戏的目的是将卡片整齐排列成图(d)的状态。请将最初的状态作为输入，在将卡片整齐排列之前，制作出输出必要的最小步骤的程序。但是，从被输入的卡的状态转移到图(d)的状态是可能的。

输入数据，1行8个数字以空白分段给出。这些表示最初状态的卡的排列。例如，图(a)的数字表示为0 7 3 4 2 5 1 6，图(c)为2 7 3 4 0 5 1 6。

input

以上述形式给出多个谜题。请处理到输入的最后。被给予的谜题的数量是1000以下。

output

关于各谜题，请将转移到最终状态的最小步骤数输出到一行。

sample input

0 1 2 3 4 5 6 7

1 0 2 3 4 5 6 7

7 6 5 4 3 2 1 0

Output for the Sample Input

0

1

28

source: https: / / onlinejudge . u - aizu.ac.jp/problems/0121

图(a) 0 7 3 4 2 5 1 6的情况图 图(b) 7 0 3 4 2 5 1 6的情况

图(c) 2 7 3 4 0 5 1 6的情况图 图(d) 0 1 2 3 4 5 6 6(最终状态)

分析：

​ 这题的确算是广度优先搜索的题目。但是它的解法不仅仅用到了广度优先搜索的知识。单独的给你一组数据去推导出最少移多少次0才可以变为01234567是很困难的。那在数学中你肯定遇到过一个概念叫做正难则反。正的推难那我们就反着推。从一开始为01234567开始每次0从某个方向移动一次所产生的字符串我们记录下来并且与0的移动数对标。我们这样反着一想，这题又是一个套模板的简单题目了。但是如何记录下来一个被访问的字符串从而在它再次被访问的时候抛弃它呢？你可能会想用一个struct做一个类型搞一个数组去遍历。但是8个数产生不一样的字符串是可以产生1万多的字符串。时间上有点慢了。所以我们可用map来存（可以去搜一下map的用法也不难，我就只说明一个c++中map是在#include中的）。（当初我去搜这题题解的时候，看到解法基本都是map的，所以说一下咯。）当然你用其他方法也行的，不过我只知道用map去ac（其他的方法懒得去试了能a就好了）。

​ 这题还有一些问题。

​ 一个是空格的字符串的输入问题。当然你可以用一个char数组去循环8次去存数反正它必然每次8个数的出现。但是你如果用string去做的话，你就要考虑这些的。我更喜欢用string下面的代码也是用string去做的。

​ 另一个是转换问题。上文我明确的说用一个字符串来标识。字符串显然是一个一维的结构，但是题中所描述的事物是一个二维的图。所以一维到二维的转换就很有必要了，这最突出的两个问题就在于二维图中的0的上移和下移这两个方向在一维结构的字符串中如何实现和二维图中不同行之间的边界问题。对于第一个突出问题，我们可以通过画图推导得出上移就是+4下移就是-4（还不懂自己画图推）。对于第二个问题，我们分两个情况来讨论。第一个情况：当0处于二维图中（0，0）或（1，3）的时候。0在二维图中这两点的时正对于一维中0和7。这对于一维来说也是边界所以当0在二维中的这两点时对于一维来说那也就只要判断0位置的变化是否0<=pos0<=7。第二种情况：当0处于二维图中的（0，3）或（1，1）的时候。这两点对应的一维位置是3和4。当处于这两点的时候（0，3）点是不能右移、（0，4）点是不能左移。既然他们有这样的要求，那么我们在判断的时候单独把这两种可能拿出来判断就可以了。

ac代码

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
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
map<string, int> m;
void init()
{
	int a[4] = { -1,1,-4,4 };
	//存移动方式。因为我们用一个一维描述二维，所以对于此题来说二维中的上就是一维的+4。还不懂的话，你可以画个图。
	queue<string> q;
	q.push("01234567");//先进入初始状态。
	m["01234567"] = 0;//最先的状态必然为移动0次。
	while (!q.empty())//套模板的循环。
	{
		string s = q.front();
		int pos0;
		q.pop();
		for (int i = 0; i < s.length(); i++)//找到0的位置，这样我们才能对0进行操作。
		{
			if (s[i] == '0')
			{
				pos0 = i;
				break;
			}
		}
		for (int i = 0; i < 4; i++)//循环遍历移动方式
		{
			string st = s;
			int t = pos0 + a[i];//移动
			if (t >= 0 && t < 8)//判断是否合法
			{
				if (pos0 == 3 && a[i] == 1)
					continue;
				if (pos0 == 4 && a[i] == -1)
					continue;
				//当0在s[3]这个位置的时候，向右移动一位到了s[4]。
				//s[4]在二维中是在第二行而s[3]是在第1行这样依然不合法
				//反过来s[4]到s[3]也是不行的。
				swap(st[pos0], st[t]);//交换
				if (m.count(st)!=1)//m中不存在st则加一。你也可以用m.find(st)==m.end()
				{
					m[st] = m[s] + 1;
					q.push(st);
				}
			}
		}
	}
}
int main()
{
	string s;
	init();
	while (getline(cin, s))
	{
		//因为有空格输入所以要用getline函数
		s.erase(remove(s.begin(), s.end(), ' '), s.end());
		//我们用的是没有空格的字符串所以要消除空格记得要加上#include<algorithm>这个头文件否则会ce错
		cout << m[s] << endl;
	}
	return 0;
}

​ 以上就是一部分我所做题目的总结。其实上面的题目都是模板题也算简单，可能地牢的三维图和7智力游戏的打表法有点难但依然还是用模板去做的。所以广度优先搜索的思想就是这样。难就难在你要知道这是广度优先并且判断合法是不能错的。我个人是推荐你用数组去存移动方向判断时就直接for循环。这样做可以减少代码量，纠错也简单。否则就像地牢那题6个方向，6次if判断是真的太多了。

​ 希望这篇文章能对你学习广度优先搜索有所帮助。