本文主要是介绍AcWing 1101.献给阿尔吉侬的花束，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：BFS
这里不用BFS进行遍历了，这里实验一种比较高效的BFS遍历：双向BFS。
其实这个双向BFS很简单，也就是说我们只要知道了终点和起点，这两个并不能少其中一个，这样我们就可以用双向BFS来节省时间。
下面是代码，大家可以参考一下，也就是多了一个遍历数组，用来识别我们是否已经双向遍历完这个地图了。
上代码;
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 505
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
char maps[MAX][MAX];
int vis[MAX][MAX];
int dist[MAX][MAX];
queue<PII>q;
int stx, sty, edx, edy;
int bfs() {vis[stx][sty] = 1;vis[edx][edy] = 2;dist[stx][sty] = 0;dist[edx][edy] = 0;q.push({ stx,sty });q.push({ edx,edy });while (!q.empty()) {auto tmp = q.front();q.pop();_for(i, 0, 4) {int a = dx[i] + tmp.first;int b = dy[i] + tmp.second;if (vis[a][b] + vis[tmp.first][tmp.second] == 3)return dist[a][b] + dist[tmp.first][tmp.second] + 1;if (maps[a][b] == '#')continue;if (a > n || a<1 || b>m || b < 1)continue;if (dist[a][b] >= 0)continue;if (vis[a][b] == -1)vis[a][b] = vis[tmp.first][tmp.second];dist[a][b] = dist[tmp.first][tmp.second]+1;q.push({ a,b });}}return -1;
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int t;cin >> t;while (t--) {cin >> n >> m;_for(i, 1, n + 1) {_for(j, 1, m + 1) {cin >> maps[i][j];}}_for(i, 1, n + 1) {_for(j, 1, m + 1) {if (maps[i][j] == 'S') {stx = i;sty = j;}else if (maps[i][j] == 'E') {edx = i;edy = j;}}}int res = 0;q = queue<PII>();memset(dist, -1, sizeof dist);memset(vis, -1, sizeof vis);res = bfs();if (res==-1)cout << "oop!" << endl;elsecout << res << endl;}return 0;
}这篇关于AcWing 1101.献给阿尔吉侬的花束的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
