题目链接: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; }