题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612
第一次做的时候我是遍历图，碰到@就bfs一次，找到两个目标点的距离之和。
但是，有可能@很多很多，会TLE！！
看了别人题解，只要两次bfs即可。
从两个起点开始bfs，记录下起点到每一个@的距离，最后遍历一次碰到@更新最小值即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 const int maxn=210; 6 int n,m; 7 char pic[maxn][maxn]; 8 int vis[maxn][maxn]; 9 int d1[maxn][maxn],d2[maxn][maxn]; 10 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 11 int best; 12 struct node 13 { 14 int x,y; 15 int dis; 16 }now,nex; 17 18 void bfs(int d[][maxn]) 19 { 20 queue<node>q; 21 q.push(now); 22 while(!q.empty()) 23 { 24 now=q.front(); 25 q.pop(); 26 if(pic[now.x][now.y]=='@') d[now.x][now.y]=now.dis; 27 for(int i=0;i<4;i++) 28 { 29 nex.x=now.x+dir[i][0]; 30 nex.y=now.y+dir[i][1]; 31 if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]!='#') 32 { 33 nex.dis=now.dis+1; 34 vis[nex.x][nex.y]=1; 35 q.push(nex); 36 } 37 } 38 } 39 return; 40 41 } 42 43 int main() 44 { 45 while(scanf("%d%d",&n,&m)!=EOF) 46 { 47 48 best=300000; 49 for(int i=0;i<n;i++) 50 scanf("%s",pic[i]); 51 for(int i=0;i<n;i++) 52 for(int j=0;j<m;j++) 53 { 54 if(pic[i][j]=='Y'){ 55 memset(vis,0,sizeof(vis)); 56 memset(d1,0,sizeof(d1)); 57 now.x=i;now.y=j;now.dis=0; 58 vis[i][j]=1; 59 bfs(d1); 60 61 } 62 if(pic[i][j]=='M'){ 63 memset(d2,0,sizeof(d2)); 64 memset(vis,0,sizeof(vis)); 65 now.x=i;now.y=j;now.dis=0; 66 vis[i][j]=1; 67 bfs(d2); 68 } 69 } 70 71 for(int i=0;i<n;i++) 72 for(int j=0;j<m;j++) 73 { 74 if(pic[i][j]=='@'&&d1[i][j]>0&&d2[i][j]>0&&best>d1[i][j]+d2[i][j]) best=d1[i][j]+d2[i][j]; 75 } 76 printf("%d ",best*11); 77 } 78 }