广搜逻辑
广搜代码核心思路
广搜伪代码
前面讲解的广度优先搜索案例都类似迷宫类的问题,但有些非迷宫类问题也可以使用广搜的思路解决
[【广搜】转弯]
【算法分析】 可以以转弯次数为依据进行广搜,这样就是每一个方向都走到尽头。特别要注意的是当这个位置访问过,还是要继续要向这个方向走,因为后面可能有没有访问过的位置。 【参考代码】 #include<bits/stdc++.h> using namespace std; char MAP[109][109]; int dir[4][2] = { -1,0,0,1,1,0,0,-1 }; struct node { int x, y, step; }l,r; bool vis[109][109]; int main() { int n; cin >> n; int sx, sy, ex, ey; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { getchar(); cin >> MAP[i][j]; } for (int j = 1; j <= n; j++) { if (MAP[i][j] == 'A') sx = i, sy = j; else if (MAP[i][j] == 'B') ex = i, ey = j; } } queue<node> q; q.push({ sx,sy,0 }); vis[sx][sy] = 1; while (q.size()) { r = q.front(); q.pop(); if (r.x == ex && r.y == ey) { cout << r.step - 1; break; } for (int i = 0; i < 4; i++) { for (int j = 1;; j++) { l.x = r.x + j * dir[i][0], l.y = r.y + j * dir[i][1], l.step = r.step + 1; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= n && MAP[l.x][l.y] != 'x' ) { if (!vis[l.x][l.y]) { vis[l.x][l.y] = 1; q.push(l); } } else break; } } } if (!vis[ex][ey]) cout << -1; return 0; }View Code
[【广搜】最小基因变化] map和set数据类型使用在下面
【算法分析】 从 start 字符串开始进行广搜,每次只变化一个字符。可以用 map 来记录达到某个字符串所需的最小次数。用 set 存储基因库,用于快速判断基因是否在基因库中。 【参考代码】 #include<bits/stdc++.h> using namespace std; int main() { string start, end; cin >> start >> end; int n; cin >> n; set<string> se; for (int i = 0; i < n; i++) { string a; cin >> a; se.insert(a); } map<string, int> mp; mp[start] = 0; queue<string> q; q.push(start); while (q.size()) { string r = q.front(); q.pop(); for (int i = 0; i < 8; i++) { string tem = r; tem[i] = 'A'; if (!mp.count(tem) && se.count(tem)) { mp[tem] = mp[r] + 1; q.push(tem); } tem[i] = 'C'; if (!mp.count(tem) && se.count(tem)) { mp[tem] = mp[r] + 1; q.push(tem); } tem[i] = 'G'; if (!mp.count(tem) && se.count(tem)) { mp[tem] = mp[r] + 1; q.push(tem); } tem[i] = 'T'; if (!mp.count(tem) && se.count(tem)) { mp[tem] = mp[r] + 1; q.push(tem); } } } if (mp.count(end)) cout << mp[end]; else cout << -1; return 0; }View Code
set集合
map容器
程序阅读题
选项
总结
标签:count,06,tem,U5,C++,int,mp,&&,push From: https://www.cnblogs.com/jayxuan/p/17844070.html