hdu 2612Find a way 两次bfs+存表

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki. Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.  Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.  Input The input contains multiple test cases.  Each test case include, first two integers n, m. (2<=n,m<=200).  Next n lines, each line included m character.  ‘Y’ express yifenfei initial position.  ‘M’    express Merceki initial position.  ‘#’ forbid road;  ‘.’ Road.  ‘@’ KCF  Output For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet. Sample Input 4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...# Sample Output 66 88 66 题意: Y和M两个人分别同乡村和城市出发，想去吃KFC，问最短时间能到达哪家KFC。 思路: 这个题我刚开始没想到要存表，我寻思着找出所有的@，然后对一个@两次bfs，找到Y 再找到M 记录到Y 和M距离的和，然后更新最小值。。。写出来 TLE了 0.0，可能是哪里没处理好。。。 对于这道题,我们可以开两个数组，从T和M分别bfs 到@存储相应位置上的@值,然后更新最小值; （更新最小值时必须Y和M都能到达@才可以！） #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define inf 0x3f3f3f3f using namespace std; int n,m; char mp[222][222]; int book[222][222]; int go[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; struct node { int x,y,step; }; int check(int x,int y) { if(x>=0 && x<m && y>=0 && y<n && mp[x][y]!='#' && book[x][y]==0) return 1; return 0; } void bfs(int l,int g,int ans[][222]) { memset(book,0,sizeof(book)); node q,p; queue<node>Q; book[l][g]=1; p.x=l; p.y=g; p.step=0; Q.push(p); while(!Q.empty()) { p=Q.front(); Q.pop(); for(int i=0;i<4;i++) { q.x=p.x+go[i][0]; q.y=p.y+go[i][1]; q.step=p.step+1; if(check(q.x,q.y)){ book[q.x][q.y]=1; if(mp[q.x][q.y]=='@') ans[q.x][q.y]=q.step; Q.push(q); } } } return ; } int main() { int i,j; int ans1[222][222],ans2[222][222]; while(~scanf("%d %d",&m,&n)) { memset(ans1,inf,sizeof(ans1)); memset(ans2,inf,sizeof(ans2)); int x1,y1,x2,y2; for (i=0;i<m;i++) { for (j=0;j<n;j++) { cin>>mp[i][j]; if(mp[i][j]=='Y') { x1=i,y1=j; } else if(mp[i][j]=='M') { x2 = i,y2 = j; } } } int minn=inf; bfs(x2,y2,ans2); bfs(x1,y1,ans1); for(i=0;i<m;i++) for(j=0;j<n;j++) { if(mp[i][j]=='@'&&ans1[i][j]!=inf&&ans2[i][j]!=inf) { minn=min(minn,ans1[i][j]+ans2[i][j]); } } printf("%d\n",minn*11); } return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！