Licae

用户名：lutaixue

访问量：4673

签　名：

剑指offer

等　　级
排　　名	5109
经　　验	1591
参赛次数	0
文章发表	9
年　　龄	18
在职情况	学生
学　　校	河南师范大学
专　　业

　　自我简介：

对算法极其感兴趣，对人工智能尤其偏爱

TA的其他文章

欧几里得算法未完全
浏览：703

深搜（新手上路）
浏览：646

宽搜（新手轻虐）
浏览：630

你可能喜欢

宽搜（新手轻虐）

　　作者: Licae　　　　发表时间：2019-07-10 17:26:03 浏览：630　|　评论：1　

# 宽搜

#### 什么是宽搜？

宽度优先搜索（BFS）也是搜索的手段之一，它与深度优先搜索类似，从某个状态出发探索所有可以到达状态。

#### 宽搜与深搜的不同之处在哪里？

与深度优先搜索的不同之处在于不搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态，也就是说，他是按照开始状态---->只需转移1次--->只需2次转移--->.........这样的顺序进行搜索，对一同一状态，宽度优先搜索只经过一次，因此复杂度为O

#### 宽搜的应用在哪里？

宽度优先搜索按照距离开始由近到远的顺序进行搜索，因此可以很容易来求最短路径问题，最少操作之类的问题。这个问题，状态仅仅是目前所在位置的坐标，当状态更加复杂是，就需要封装成一个类来表达状态了，转移的方式为四个方向移动，状态数与迷宫的大小是相等的，所以复杂度是O(N * M) 
![](/image_editor_upload/20190710052531_69009.png)

#### 实战一下

[**[蓝桥杯][2015年第六届真题]穿越雷区**](<https://www.dotcpp.com/oj/problem1825.html>)

```c++
#include<iostream>
#include<stdio.h>
using namespace std;
char mmap[150][150];//地图 
bool book[150][150];//标记走过的地方
int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//变换顺序右下左上 
bool ff = false;//用来判断终止条件
typedef struct node{
	int x,y,step;
	char flag;
}node;//存放步数，坐标，和当前位置的状态

node n[10500];//开的大一点 
int main(){
	int m;
	cin >> m;
	getchar();//输入m后吃掉回车
	int head,tail,x,y,tx,ty;
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= m;j++){
			scanf("%c",&mmap[i][j]);
			if(mmap[i][j] == 'A'){
				x = i;
				y = j;
			}
			getchar();
		}
	}
	head = 1,tail = 1;//初始化队列的头尾 
	n[tail].x = x;
	n[tail].y = y;
	n[tail].step = 0;
	n[tail].flag = ' ';
	book[x][y] = 1;//标记A点走过，不会再回来
	tail++;
	//深搜核心
	while(head < tail){
		for (int i = 0;i < 4;i++){
			tx = n[head].x + next[i][0];
			ty = n[head].x + next[i][1];
			//判断是否越界
			if(tx > m || ty < 1)
				continue;
			if(ty > m || ty < 1)
				continue;
			//判断是否符合条件 
			if(book[tx][ty] == 0 && n[head].flag != mmap[tx][ty]){
				book[tx][ty] = 1;
				n[tail].y = ty;
				n[tail].x = tx;
				n[tail].step = n[head].step + 1;
				n[tail].flag = mmap[tx][ty];
				tail++;
			}
		}
		if(n[head].flag == 'B'){
			cout << n[head].step;
			ff = true;
			break;
		}
		head++;
	} 
	if(!ff)
		cout << -1;
	system("pause");
	return 0;
}
```

**此处做一下说明：**

上述代码有一些BUG，但是一直解决不了，仅供参考思路

0.0分

39 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

验题君

感觉叫广搜更好点

2019-07-10 21:27:19

Licae

TA的其他文章

你可能喜欢

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

【矩阵】（C语言代码）

校门外的树（C语言代码）

C二级辅导-公约公倍（C语言代码）

宽搜（新手轻虐）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

最小公倍数（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1054题解

Quadratic Equation （C语言代码）

一元一次方程（C语言代码）

淘淘的名单（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Licae

TA的其他文章

你可能喜欢

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

【矩阵】 （C语言代码）

校门外的树 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

宽搜（新手轻虐）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

最小公倍数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1054题解

Quadratic Equation （C语言代码）

一元一次方程 （C语言代码）

淘淘的名单 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

求圆的面积（C语言代码）

【矩阵】（C语言代码）

校门外的树（C语言代码）

C二级辅导-公约公倍（C语言代码）

　　评论区

最小公倍数（C语言代码）

一元一次方程（C语言代码）

淘淘的名单（C语言代码）