题意：就是Y和M在@相遇的最短的时间。
思路：基本的广搜题，先Y搜一次，然后M搜一次，最后求出Y和M在@相遇的最短的时间。
代码实现：
#include<iostream> #include<queue> #include<cstring> using namespace std; int n,m,count1[210][210],count2[210][210],visited[210][210];//count1记录的是Y到各个点的最短的时间 int b[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//count2记录的是M到各个点最短的时间 char str[210][210]; struct node{ int x; int y; }; int nima(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m&&str[x][y]!='#'&&visited[x][y]==0) return 1; else return 0; } void bfs(int flag,int x,int y) { int f=0,r=0,t1,t2; node p,temp; queue<node>q; p.x=x;p.y=y; q.push(p); if(flag==1) { while(!q.empty())//基本的广搜，此时我用的是队列，此前我用的一直是数组，还是队列好多了 { p=q.front(); q.pop(); for(int i=0;i<4;i++) { t1=p.x+b[i][0];t2=p.y+b[i][1]; if(nima(t1,t2)) { visited[t1][t2]=-1; temp.x=t1; temp.y=t2; q.push(temp); count1[t1][t2]=count1[p.x][p.y]+11; } } } } else { while(!q.empty()) { p=q.front(); q.pop(); for(int i=0;i<4;i++) { t1=p.x+b[i][0];t2=p.y+b[i][1]; if(nima(t1,t2)) { visited[t1][t2]=-1; temp.x=t1; temp.y=t2; q.push(temp); count2[t1][t2]=count2[p.x][p.y]+11; } } } } } int main() { int i,j,x1,y1,x2,y2,a[40005][2],num,flag,min; while(scanf("%d%d",&n,&m)!=EOF) { getchar(); num=0;min=100000000; for(i=0;i<n;i++) scanf("%s",str[i]); for(i=0;i<n;i++) { for(j=0;j<m;j++) { count1[i][j]=0; count2[i][j]=0; visited[i][j]=0; if(str[i][j]=='Y') { x1=i; y1=j; } else if(str[i][j]=='M') { x2=i; y2=j; } else if(str[i][j]=='@') { a[num][0]=i; a[num][1]=j; num++; } } } flag=1; visited[x1][y1]=-1; bfs(flag,x1,y1); memset(visited,0,sizeof(visited)); flag=2; visited[x2][y2]=-1; bfs(flag,x2,y2); for(i=0;i<num;i++) { if(count1[a[i][0]][a[i][1]]!=0&&count2[a[i][0]][a[i][1]]!=0)//@必须是Y和M都能到达的，否则容易出错的哦 { if(min>(count1[a[i][0]][a[i][1]]+count2[a[i][0]][a[i][1]])) min=count1[a[i][0]][a[i][1]]+count2[a[i][0]][a[i][1]]; } } printf("%d\n",min); } return 0; }