?題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

思路：從兩個起點出發，有多個終點，求從兩個起點同時能到達的終點具有的最小時間，開兩個數組分別保存兩個起點到達每一個終點的用時，最后將兩個

數組里的時間加起來求最小的一組，必須對應相加，因為終點必須同時到達。

?

#include <iostream> #include <string> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> #include <sstream> #include <cstdlib> #include <fstream> #include <queue> using namespace std; struct node{int x,y,step; }a[1010]; node p,q; int n,m,sx1,sy1,sx2,sy2,ans1[1010],ans2[1010],ans[1010]; int mmin,cnt; int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; char maze[205][205]; bool visit[205][205]; int judge(int x,int y){for(int i=1;i<cnt;i++){if(x==a[i].x&&y==a[i].y)return i;}return 0; } void bfs1(int x,int y){memset(ans,0,sizeof(ans));memset(ans1,-1,sizeof(ans1));memset(visit,0,sizeof(visit));queue<node> Q;p.x=x;p.y=y;p.step=0;Q.push(p);visit[p.x][p.y]=1;while(!Q.empty()){p=Q.front();Q.pop();int num=judge(p.x,p.y);if(num){ans[num]=p.step;visit[p.x][p.y]=1;}for(int i=0;i<4;i++){q.x=p.x+dir[i][0];q.y=p.y+dir[i][1];q.step=p.step+1;if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;if(visit[q.x][q.y])continue;if(maze[q.x][q.y]=='#')continue;Q.push(q);visit[q.x][q.y]=1;}}for(int i=1;i<cnt;i++){if(ans[i])ans1[i]=ans[i];}} void bfs2(int x,int y){memset(ans,0,sizeof(ans));memset(ans2,-1,sizeof(ans2));memset(visit,0,sizeof(visit));queue<node> Q;p.x=x;p.y=y;p.step=0;Q.push(p);visit[p.x][p.y]=1;while(!Q.empty()){p=Q.front();Q.pop();int num=judge(p.x,p.y);if(num){ans[num]=p.step;visit[p.x][p.y]=1;}for(int i=0;i<4;i++){q.x=p.x+dir[i][0];q.y=p.y+dir[i][1];q.step=p.step+1;if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;if(visit[q.x][q.y])continue;if(maze[q.x][q.y]=='#')continue;Q.push(q);visit[q.x][q.y]=1;}}for(int i=1;i<cnt;i++){if(ans[i])ans2[i]=ans[i];} } int main() {//ifstream fin;//fin.open("data1.txt");while(cin>>n>>m){cnt=1;for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>maze[i][j];if(maze[i][j]=='Y'){sx1=i;sy1=j;}if(maze[i][j]=='M'){sx2=i;sy2=j;}if(maze[i][j]=='@'){a[cnt].x=i;a[cnt++].y=j;}}mmin=999999;bfs1(sx1,sy1);bfs2(sx2,sy2);for(int i=1;i<cnt;i++){if(ans1[i]!=-1&&ans2[i]!=-1){int tsum=ans1[i]+ans2[i];if(mmin>tsum)mmin=tsum;}}cout<<mmin*11<<endl;}return 0;}

?

?

轉載于:https://www.cnblogs.com/snake-hand/p/3144771.html

總結

以上是生活随笔為你收集整理的HDU/HDOJ 2612 Find a way 双向BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。