BFS搜索总结

BFS搜索体会

- 前言
第一种：搜索数量（岛屿类问题）
- 第一题
- 算法详情
- 代码详情
- 第二题
- 算法详情
- 代码详情
第二种：求操作步骤
- 第一题
- 算法详情
- 代码详情
- 第二题
- 算法详情
- 代码详情
第三种：三维搜索
- 算法详解
- 代码详情
最小操作数总结：BFS队列 + 结构体存储特点
- 先回顾第二种的第一题：
- 回顾我卡的那道题

前言

广度优先搜索（Breadth-First Search，BFS，或宽度优先搜索）是基本的暴力技术，常用于解决图、树的遍历。在实际编程中，一般使用队列实现，下面用几个题介绍基础使用。

第一种：搜索数量（岛屿类问题）第一题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1312
hdu 1312 “Red and Black”
题目翻译如下:
有一个长方形的房间，铺着方形瓷砖，瓷砖为红色或黑色。一个人站在黑色瓷砖上，他可以按上、下、左、右方向移动到相邻的瓷砖。但他不能在红色瓷砖上移动，只能在黑色瓷砖上移动。编程计算他可以到达的黑色瓷砖的数量。

输入:第1行包含两个正整数W和H,W和H分别表示x方向和y方向上的瓷砖数量。W和H均不超过20。下面有H行，每行包含w个字符。每个字符表示一片瓷砖的颜色。用符号表示如下:“。”表示黑色瓷砖;“#”表示红色瓷砖;“@”代表黑色瓷砖上的人,在数据集中只出现一次。

输出:一个数字，这个人从初始瓷砖能到达的瓷砖总数量(包括起点)。

算法详情

很基础的搜索问题，只需要对起点进行上，下，左，右的暴力搜索即可（在题目中一般都是按照左，上，右，下的顺序搜索的），符合要求的坐标入队并标记已经搜索过的位置，模拟队列出入的过程，这里给大家模拟一下。

再给大家放一个树状图（后面会提到）

代码详情

这里结构体储存的是坐标，还可以使用pair储存

#include
using namespace std;
char room[100][100]; // 房间容量
int row, col, num; //房间的规格, 记录格子的个数
#define CHECK(h, z) (h >= 0 && h < row && z >= 0 && z < col) // 检查是否在房间中
struct node {
	int x;
	int y;
};
int dir[4][2] = {
	{-1, 0}, // 向左
	{0, -1}, // 向上
	{1, 0}, // 向右
	{0, 1} // 向下
};
void bfs(int dx, int dy) { // 传进来的是起点坐标
	num = 1; // 起点也算
	node start, next;
	queue q;
	start.x = dx, start.y = dy;
	q.push(start);
	while(!q.empty()) {
		start = q.front(); // 将队列中的点带出来进行四个方向的检查
		q.pop(); // 移除带出来的点
		for(int i = 0; i < 4; i++) {
			int h = start.x + dir[i][0];
			int z = start.y + dir[i][1];
			if(CHECK(h, z)&& room[h][z] == '.') {
				num++;
				next.x = h, next.y = z;
				q.push(next);
				room[h][z] = '#';
			}
		}
	}
}

int main() {
	int dx, dy;
	cin >> row >> col;
	for(int i = 0; i < row; i++) {
		for(int j = 0; j < col; j++) {
			cin >> room[i][j];
			if(room[i][j] == '@') {
				dx = i, dy = j;
			}
		}
	}
	bfs(dx, dy);
	cout << num < 
第二题 
题目链接：https://leetcode.cn/problems/number-of-islands/
 LeetCode：岛屿的数量 
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 此外，你可以假设该网格的四条边均被水包围。 
示例 1： 
输入：grid = [
 [“1”,“1”,“1”,“1”,“0”],
 [“1”,“1”,“0”,“1”,“0”],
 [“1”,“1”,“0”,“0”,“0”],
 [“0”,“0”,“0”,“0”,“0”]
 ]
 输出：1
 示例 2： 
输入：grid = [
 [“1”,“1”,“0”,“0”,“0”],
 [“1”,“1”,“0”,“0”,“0”],
 [“0”,“0”,“1”,“0”,“0”],
 [“0”,“0”,“0”,“1”,“1”]
 ]
 输出：3 
算法详情 
和上一题相似，不同的是岛屿的数量计数有技巧。 
代码详情 
class Solution {
public:
    int dir[4][2] = {
        {-1, 0},
        {0, -1},
        {1, 0},
        {0, 1}
    };
    int numIslands(vector>& grid) {
        int row = grid.size(), col = grid[0].size(), cnt = 0;
        queue> q;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == '1') {
                    cnt++;
                    grid[i][j] = '0';
                    pair start;
                    q.push({i, j});
                    while(!q.empty()) {
                        auto start = q.front();
                        q.pop();
                        for(int k = 0; k < 4; k++) {
                            int dx = start.first + dir[k][0];
                            int dy = start.second + dir[k][1];
                            if(dx >= 0 && dx < row && dy >= 0 && dy < col && grid[dx][dy] == '1') {
                                q.push({dx, dy});
                                grid[dx][dy] = '0';
                            }
                        }
                    }
                }
            }
        }
        return cnt;
    }
};
 
第二种：求操作步骤 
链接：http://poj.org/problem?id=3278
 题目翻译： 
第一题 
农场主约翰已被告知一头逃亡母牛的位置，并希望立即抓住她。他从N（0）点开始≤ N≤ 100000），奶牛位于K点（0≤ K≤ 100000）在同一号码线上。农夫约翰有两种交通方式：步行和远程传送。 
步行：FJ可以在一分钟内从任意点X移动到点X-1或X+1
 传送：FJ可以在一分钟内从任意点X移动到点2×X。 
如果母牛没有意识到它的追赶，根本不动，农夫约翰需要多长时间才能找回它？ 
算法详情 
看似与前两题很像，而且变成了一维的，但是题目要求的是最小追赶到母牛的最小时间
 如何去求最小时间？，可能大家第一反应是用min函数不断去更新时间，如何去更新？，我们用的是BFS搜索，BFS搜索的方式和二叉树的层次遍历很相似，这里我们借助第一题的树状图，我称它为搜索树（名词我大都不是特别在意哈哈！），当时我还卡在时间更新问题上（终究是才入门哈哈！）
 
 第一层的操作数始终为1，第二层操作数为2，第三层为3，第四层为4。如何做到呢？我们可以用结构体辅助（看别人的代码学到的），这里放个代码。 
#include
using namespace std;

struct node {
	int x;
	int sum;
};

node a, b, c;
int main() {
	queue q;
	c.x = 1;
	c.sum = 0;
	q.push(c);
	while(!q.empty()) {
		a = q.front();
		q.pop();
		b = a;
		if(b.x++) {
			b.sum++;
			q.push(b);
			printf("%dn", b.sum);
			if(b.sum == 4) {
				return 0;
			}
		}
		b = a;
		if(b.x++) {
			b.sum++;
			q.push(b);
			printf("%dn", b.sum);
			if(b.sum == 4) {
				return 0;
			}
		}
	}
}
 
运行结果
 
 我们将它展开为树状图
 
 大家可能还是会纠结如何去求最小时间，BFS的特点就是在搜索树中一层一层的找每一层从左到右，那么最先搜索到的目标状态（一般都会有多个合法状态，所以又得题目才会要求最小操作数）肯定就是第一个合法的状态。但是上述代码如何实现的呢，而且操作数是随着层数变化的，通过代码我们可以看出同一个变量被用了两次，那么每一个元素出队都会产生两个分支，而且出队的元素只要相同那么就会被放在同一层，请大家自行理解这样的方式。 
代码详情 
读者自行理解 
#include
#include
#include
using namespace std;
struct node {
	int location;
	int time;
};
node a, b, c;
int start, en;
int flag[100001] = {0};
int bfs(int start, int end) {
	a.location = start, a.time = 0;
	queue q;
	q.push(a);
	if(start >= end) {
		return start - end;
	}
	memset(flag, 0, sizeof(flag));
	while(!q.empty()) {
		b = q.front();
		q.pop();
		c = b;
		c.location++;
		if(c.location <= 100000 && !flag[c.location]) {
			c.time++, q.push(c);
			flag[c.location] = 1;
			if(c.location == end) {
				return c.time;
			}
		}
		c = b;
		c.location--;
		if(c.location <= 100000 && !flag[c.location]) {
			c.time++, q.push(c);
			flag[c.location] = 1;
			if(c.location == end) {
				return c.time;
			}
		}
		c = b;
		c.location *= 2;
		if(c.location <= 100000 && !flag[c.location]) {
			c.time++ ,q.push(c);
			flag[c.location] = 1;
			if(c.location == end) {
				return c.time;
			}
		}
	}
}
int main() {
	while(~scanf("%d%d", &start, &en)) {
		int ans = bfs(start, en);
		printf("%dn", ans);
	}
	return 0;
}
 
第二题 
链接: http://poj.org/problem?id=3414
 题目翻译：
 你会得到两个罐子（编号为1，2），分别有A和B升的容量。可以执行下列操作： 
填充：把1号或者2号任意一个装满；
 倒掉：把1号或者2号任意一个倒空；
 转移：将1号倒入2号（也可以是2号倒入1号）；在此操作后，要么一个罐子满，要么一个罐子空。
 编写一个程序，以找到这些操作的最少次数（使得1号或者2号产生C升水）。 
输入：A，B，C。（A，B为最大容量，C为目标水量）一开始的状态A，B都没有水 
算法详情 
和上一题如出一辙，但要理解这种重复的操作步骤，不要管他，只要是没有搜索到的状态通通入队。 
代码详情 
#include
using namespace std;
int a, b, c, tim = 0;
int flag[100][100] = {0};
struct state {
	int x;
	int y;
	int tim;
};
state o, s, t;
int bfs(int xv, int yv) {
	o.tim = 0, o.x = xv, o.y = yv;
	queue q;
	q.push(o);
	memset(flag, 0, sizeof(flag));
	while(!q.empty()) {
		s = q.front();
		q.pop();
		t = s, t.tim++, t.x = a, t.y = s.y; // 将a装满
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
		t = s, t.tim++, t.x = s.x, t.y = b; // 将b装满
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
		t = s, t.tim++, t.x = 0, t.y = s.y; // 将a倒掉
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
		t = s, t.tim++, t.x = s.x, t.y = 0; // 将b倒掉
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
		t = s, t.tim++, t.x = min(a, t.x + t.y), t.y -= min(t.y, a - s.x); // 从b -> a
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
		t = s, t.tim++, t.y = min(b, t.x + t.y), t.x -= min(t.x, b - s.y); // 从 a -> b
		if(t.x == c || t.y == c) {
			return t.tim;
		}
		if(!flag[t.x][t.y]) {
			flag[t.x][t.y] = 1;
			q.push(t);
		}
	}
}
int main() {
	cin >> a >> b >> c;
	int ans = bfs(0, 0);
	printf("%dn", ans);
	return 0;
}
 
这里没有考虑能否产生C升水的情况，即A，B各自容量是否大于等于C
 这代码看着很复杂因为操作数多，如果是求可能的状态，那么用DFS就很好解。 
第三种：三维搜索 
题目链接:：http://acm.hdu.edu.cn/showproblem.php?pid=1240 
第一次遇见三维数组的时候还是初学DP的时候遇见的。
 题目翻译：
 你在太空中驾驶宇宙飞船，你的目标是通过上，下，左，右，前，后从起点坐标到指定坐标的最小移动步数，不能到达指定点则输出NO ROUTE。大家点击链接，看到输入样例可能会有点懵，我当时也是哈哈哈。给大家解释这个样例就能懂了。
 
 哈哈哈这个图我笑了，但是就是这样哈哈哈，我相信大家懂起了。这里大家可以自行去了解三维数组，这个在数据结构中的数组与广义表中有介绍。 
算法详解 
这不就是结合第一种第二种的小小升级版吗？不要害怕上下，无非多了两个搜索方向，不用管，只要是新状态统统入队。 
代码详情 
#include
using namespace std;
int dir[6][3] = {
	{1, 0, 0}, //向前
	{-1, 0, 0}, //向后
	{0, 1, 0}, // 向左
	{0, -1, 0}, //向右
	{0, 0, 1}, //向上
	{0, 0, -1} // 向下
};
int N, stax, stay, staz, endx, endy, endz;
char space[11][11][11];
struct position {
	int x;
	int y;
	int z;
	int time;
};
position a, b, c;
#define CHECK(x, y, z) (x >= 0 && x < N && y >= 0 && y < N && z >= 0 && z < N)
int bfs(int xc, int yc, int zc) {
	queue q;
	a.x = xc, a.y = yc, a.z = zc, a.time = 0;
	q.push(a);
	while(!q.empty()) {
		b = q.front();
		q.pop();
		for(int i = 0; i < 6; i++) {
			int dx = b.x + dir[i][0];
			int dy = b.y + dir[i][1];
			int dz = b.z + dir[i][2];
			int tim = b.time + 1;
			if(CHECK(dx, dy, dz) && space[dx][dy][dz] == 'O') {
				c.x = dx, c.y = dy, c.z = dz, c.time = tim;
				q.push(c);
				space[dx][dy][dz] = 'X';
			}
			if(dx == endx && dy == endy && dz == endz) {
				return tim;
			}
		}
	}
	printf("NO ROUTEn");
	exit(0);
}
int main() {
	cin >> N;
	for(int i = 0 ; i < N; i++) { // z坐标
		for(int j = 0; j < N; j++) { // x 坐标
			for(int k = 0; k < N; k++) { // y 坐标
				cin >> space[i][j][k];
			}
		}
	}
	cin >> stax >> stay >> staz;
	cin >> endx >> endy >> endz;
	int ans = bfs(stax, stay, staz);
	printf("%dn", ans);
	return 0;
}
}
 
这里我在更新最小操作数的时候卡了一下。所以接下来我打算总结一下关于最小操作数。 
最小操作数总结：BFS队列 + 结构体存储特点 
先回顾第二种的第一题： 
我们用的是结构体储存数据，因为数据不止一种，现在我们来想这道题如何去设置框架，首先结构体中肯定要储存当前的位置和操作次数（和分钟等价，大家莫在意）我们现在只关注操作次数，初始化要赋值为0，那么初始点入队列，入队后并出队然后pop掉，下面就分三步。
 **1：**往右移动一步，那么结构体中的位置也要移动，并且操作次数 + 1，如果移动的位置合法则入队，并将该点设置为已访问。
 2往左移动一步，同理，但是大家会想，那我不白移动了，而且操作次数 = 2了，莫慌，这里我们这样操作 
while(!q.empty()) {
	a = q.front();
	q.pop();
	//我们要让下一次不接着用上一次移动的值，而是使用才出队的新值。（后面还会有新问题莫慌）
	//往右移动
	c = a;
	
	//左移动我们也用c = a；
	c = a;
	//操作省略
	// * 2 右移动
	c = a;
	//解释：我们每次入队列的结构体都是新的值互不影响
	//ok 假设我们从初始点入队了两个结构体：其中他们的操作数肯定都是1
	//好！又来循环一次，出队 操作数 + 1 = 2（这里是右移）。+ 1 = 2（左移）
	//大家如果在脑海中模拟队列的情况和产生的那颗搜索树就能很快明白，然后结合BFS的搜索方式
 
第二题也是类似的，不过时间的更新有优化，大家可以自行思考。 
回顾我卡的那道题 
大家可能会注意到我是直接引用的 b = q.front() 中的b来进行搜索的，但是我在入队的时候是用的新的结构体入队的。两种方式本质相同。希望大家看了我的文章有所帮助，后面我会整理DFS与回溯！

BFS搜索总结

C/C++/C#相关栏目本月热门文章