Problem Description
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
?
bfs求出兩個人到各個點的距離，最后枚舉最短的距離。用c++提交WA，G++提交AC了，這是什么原因。。。
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 15 using namespace std; 16 #define PI acos(-1.0) 17 #define max(a,b) (a) > (b) ? (a) : (b) 18 #define min(a,b) (a) < (b) ? (a) : (b) 19 #define ll long long 20 #define eps 1e-10 21 #define MOD 1000000007 22 #define N 206 23 #define inf 1e12 24 int n,m; 25 char mp[N][N]; 26 struct Node{ 27 int x,y; 28 int t; 29 }st1,st2; 30 int vis[N][N]; 31 int dirx[]={0,0,-1,1}; 32 int diry[]={-1,1,0,0}; 33 int dist1[N][N]; 34 int dist2[N][N]; 35 void bfs1(Node st){ 36 memset(vis,0,sizeof(vis)); 37 queue<Node>q; 38 q.push(st); 39 vis[st.x][st.y]=1; 40 41 Node t1,t2; 42 while(!q.empty()){ 43 t1=q.front(); 44 q.pop(); 45 for(int i=0;i<4;i++){ 46 t2.x=t1.x+dirx[i]; 47 t2.y=t1.y+diry[i]; 48 if(mp[t2.x][t2.y]=='#') continue; 49 if(t2.x<0 || t2.x>=n || t2.y<0 || t2.y>=m) continue; 50 if(vis[t2.x][t2.y]) continue; 51 vis[t2.x][t2.y]=1; 52 t2.t=t1.t+1; 53 dist1[t2.x][t2.y]=t2.t; 54 q.push(t2); 55 } 56 } 57 } 58 void bfs2(Node st){ 59 memset(vis,0,sizeof(vis)); 60 queue<Node>q; 61 q.push(st); 62 vis[st.x][st.y]=1; 63 64 Node t1,t2; 65 while(!q.empty()){ 66 t1=q.front(); 67 q.pop(); 68 for(int i=0;i<4;i++){ 69 t2.x=t1.x+dirx[i]; 70 t2.y=t1.y+diry[i]; 71 if(mp[t2.x][t2.y]=='#') continue; 72 if(t2.x<0 || t2.x>=n || t2.y<0 || t2.y>=m) continue; 73 if(vis[t2.x][t2.y]) continue; 74 vis[t2.x][t2.y]=1; 75 t2.t=t1.t+1; 76 dist2[t2.x][t2.y]=t2.t; 77 q.push(t2); 78 } 79 } 80 } 81 int main() 82 { 83 while(scanf("%d%d",&n,&m)==2){ 84 memset(dist1,0,sizeof(dist1)); 85 memset(dist2,0,sizeof(dist2)); 86 for(int i=0;i<n;i++){ 87 scanf("%s",mp[i]); 88 for(int j=0;j<m;j++){ 89 if(mp[i][j]=='Y'){ 90 st1.x=i; 91 st1.y=j; 92 st1.t=0; 93 } 94 if(mp[i][j]=='M'){ 95 st2.x=i; 96 st2.y=j; 97 st2.t=0; 98 } 99 } 100 } 101 102 bfs1(st1); 103 bfs2(st2); 104 105 int ans=inf; 106 for(int i=0;i<n;i++){ 107 for(int j=0;j<m;j++){ 108 if(mp[i][j]=='@'){ 109 if(dist1[i][j]!=0 && dist2[i][j]!=0){ 110 int sum=dist1[i][j]+dist2[i][j]; 111 if(sum<ans){ 112 ans=sum; 113 } 114 } 115 116 } 117 } 118 } 119 printf("%d\n",ans*11); 120 121 122 } 123 return 0; 124 }
?
?
分組表格控件--GroupingGrid（轉）)
