bfs的核心思想就是把一些问题抽象成图,从一个点开始,向四周开始扩散。
一般使用队列这种数据结构,每次将一个节点周围所有节点加入队列。
相较于dfs,bfs找到的路径一定是最短的,但代价就是空间复杂度比dfs大很多。
从一个起点走到终点,问最短路径,这就是bfs的本质。
下面为bfs大致模板
int bfs() { 初始化队列 初始化距离为-1 将起点距离设为0,并加入队列 while(队列非空){ 弹出队头元素 遍历所有方向 if(符合条件){ 更新距离 将相邻节点加入队列 } } return 距离 }
模板题1[走迷宫]
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 #define x first 6 #define y second 7 8 typedef pair<int, int> PII; 9 10 const int N = 110; 11 12 int n, m; 13 int g[N][N], d[N][N]; 14 15 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; 16 17 int bfs() 18 { 19 queue<PII> q; 20 memset(d, -1, sizeof d); 21 d[0][0] = 0; 22 q.push({0, 0}); 23 while(!q.empty()){ 24 auto t = q.front(); 25 q.pop(); 26 for( int i = 0; i < 4; i++ ){ 27 int x = t.x+dx[i], y = t.y+dy[i]; 28 if(x >= 0 && x < n && y >= 0 && y < m && d[x][y]==-1 && g[x][y]==0){ 29 d[x][y] = d[t.x][t.y]+1; 30 q.push({x, y}); 31 } 32 } 33 } 34 35 return d[n-1][m-1]; 36 } 37 38 int main() 39 { 40 scanf("%d%d", &n, &m); 41 for( int i = 0; i < n; i++ ) 42 for( int j = 0; j < m; j++ ) 43 scanf("%d", &g[i][j]); 44 printf("%d\n", bfs()); 45 46 return 0; 47 }
模板题2[八数码]
在一个 3×33×3 的网格中,1∼81∼8 这 88 个数字和一个 x
恰好不重不漏地分布在这 3×33×3 的网格中。
例如:
1 2 3
x 4 6
7 5 8
在游戏过程中,可以把 x
与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 x
例如,示例中图形就可以通过让 x
先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行,将 3×33×3 的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个整数,表示最少交换次数。
如果不存在解决方案,则输出 −1−1。
输入样例:
2 3 4 1 5 x 7 6 8
输出样例
19
题解:
将3*3的矩阵转化成字符串,从初始状态到最终状态求最短路
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; 6 7 int bfs(string s) 8 { 9 //目标状态 10 string end = "12345678x"; 11 queue<string> q; 12 unordered_map<string, int> dis; 13 q.push(s); 14 dis[s] = 0; 15 while(!q.empty()){ 16 string t = q.front(); 17 q.pop(); 18 int dist = dis[t]; 19 if(t==end) 20 return dist; 21 //查询x在字符串中的下标,然后转化为矩阵中的坐标 22 int k = t.find('x'); 23 int x = k/3, y = k%3; 24 for( int i = 0; i < 4; i++ ){ 25 int a = x+dx[i], b = y+dy[i]; 26 if(a >= 0 && a < 3 && b >= 0 &&b < 3){ 27 //转移x 28 swap(t[k], t[a*3+b]); 29 if(!dis.count(t)){//t状态没有出现过 30 q.push(t); 31 dis[t] = dist+1; 32 } 33 //还原状态 ,为下一种转换做准备 34 swap(t[k], t[a*3+b]); 35 } 36 } 37 } 38 39 return -1; 40 } 41 42 int main() 43 { 44 string c, s; 45 for( int i = 0; i < 9; i++ ){ 46 cin>>c; 47 s+=c; 48 } 49 cout<<bfs(s)<<endl; 50 51 return 0; 52 }