广搜逻辑
广搜代码核心思路
广搜伪代码
思维导图
1、[【广搜】走迷宫]
求最少需要多少步,考虑使用广搜。从起点开始进行搜索,规则只能向上下左右走动,当搜索到终点时就结束。
广搜的核心思路:
初始化一个队列和数组
将起点入队并标记
当队列不为空且没到终点的时候
取出队首(有需要课进项处理)
队首元素为入过队的邻居入队
【算法分析】 求最少需要多少步,考虑使用广搜。从起点开始进行搜索,规则只能向上下左右走动,当搜索到终点时就结束。 【参考代码】 #include <bits/stdc++.h> using namespace std; char MAP[49][49]; bool vis[49][49]; struct node { int x, y, step; }l,r; int dir[4][2] = { {-1,0} ,{0,1},{1,0},{0,-1} }; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> MAP[i] + 1; } queue<node> q; q.push({ 1,1,1 }); vis[1][1] = 1; while (q.size()) { r = q.front(); q.pop(); if (r.x == n && r.y == m) { cout << r.step; break; } for (int i = 0; i < 4; i++) { l.x = r.x + dir[i][0]; l.y = r.y + dir[i][1]; l.step = r.step + 1; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && !vis[l.x][l.y] && MAP[l.x][l.y] == '.') { vis[l.x][l.y] = 1; q.push(l); } } } return 0; }
2、[【广搜】走出迷宫]
【算法分析】 求最少需要多少步,考虑使用广搜。从起点开始进行搜索,规则只能向上下左右走动,当搜索到终点时就结束。 【参考代码】 #include <bits/stdc++.h> using namespace std; char MAP[109][109]; bool vis[109][109]; struct node { int x, y, step; }l,r; int dir[4][2] = { {-1,0} ,{0,1},{1,0},{0,-1} }; int main() { int n, m; cin >> n >> m; int sx, sy, tx, ty; for (int i = 1; i <= n; i++) { cin >> MAP[i] + 1; for (int j = 1; j <= m; j++) { if (MAP[i][j] == 'S') { sx = i, sy = j; } else if (MAP[i][j] == 'T') { tx = i, ty = j; } } } queue<node> q; q.push({ sx,sy,0 }); vis[sx][sy] = 1; while (q.size()) { r = q.front(); q.pop(); if (r.x == tx && r.y == ty) { cout << r.step; return 0; } for (int i = 0; i < 4; i++) { l.x = r.x + dir[i][0]; l.y = r.y + dir[i][1]; l.step = r.step + 1; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && !vis[l.x][l.y] && MAP[l.x][l.y] != '#') { vis[l.x][l.y] = 1; q.push(l); } } } cout << -1; return 0; }
3、[【广搜】马的遍历]
【算法分析】 从马的位置开始广搜,由于求得是最少次数,则每个点只需要访问一次,并且在广搜的过程中记录次数。 【参考代码】 #include <bits/stdc++.h> using namespace std; int dis[409][409]; int dir[8][2] = { -2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2 }; struct node { int x, y; }l,r; int main() { memset(dis, -1, sizeof(dis)); int n, m, x, y; cin >> n >> m >> x >> y; dis[x][y] = 0; queue<node>q; q.push({ x,y }); while (q.size()) { r = q.front(); q.pop(); for (int i = 0; i < 8; i++) { l.x = r.x + dir[i][0]; l.y = r.y + dir[i][1]; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && dis[l.x][l.y] == -1) { dis[l.x][l.y] = dis[r.x][r.y] + 1; q.push({ l.x,l.y }); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << dis[i][j] << " "; } cout << '\n'; } return 0; }
4、水洼计数
【算法分析】 求一个连通块可以从连通块中的任意一个位置开始,广搜去标记所有与其连通的位置。求图中的连通块个数,可以遍历这个图,碰到一个没有标记的位置且这个位置有水,则从这个位置开始广搜。 【参考代码】 #include <bits/stdc++.h> using namespace std; char MAP[119][119]; bool vis[119][119]; int dir[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} }; int n, m; struct node { int x, y; }l,r; void bfs(int x, int y) { vis[x][y] = 1; queue<node> q; q.push({ x,y }); while (q.size()) { r = q.front(); q.pop(); for (int i = 0; i < 8; i++) { l.x = r.x + dir[i][0]; l.y = r.y + dir[i][1]; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && !vis[l.x][l.y] && MAP[l.x][l.y] == 'W') { vis[l.x][l.y] = 1; q.push({ l.x,l.y }); } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> MAP[i] + 1; } int number = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!vis[i][j] && MAP[i][j] == 'W') { number++; bfs(i, j); } } } cout << number; return 0; }
深搜广搜对比