hdoj2612 Find a Way BFS

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

题目大意：就是两个人找个KFC约会，使得这两个人走过的步数之和最短。

刚开始我的思路是这样：从每个KFC出发，分别搜索到A,B的最短距离之和，再选择最短距离之和的最小值，可是很不幸TLE了，而且因为我在函数外开了一个全局变量，粗心在函数内又开了一次，WA到让人怀疑人生。还不容易过了样例，却又TLE。杯具！  后来我又想到，可不可以从正向分别搜A,B到图中每一个点的最小的步数，两次的结果加起来。最后再遍历一遍，如果那个地方有KFC，就取那个地方的值，这样就不会TLE了，而且明显要简单一些。

code:

#include<cstdio> #include<iostream> #include<queue> #include<cstring> #define min(a,b) (a<b?a:b) using namespace std; int N,M,visit[205][205],res,step[205][205];//step记录步数，visit标记是否访问过，而且不改变原地图 const int INF=99999999; char a[205][205];//a为地图。 struct node{     int x,y,step; }Yi,Mer,s; int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1}; void bfs(){     queue<node>q;     while(!q.empty())q.pop();     memset(visit,0,sizeof(visit));     q.push(s);     while(!q.empty()){         node ne=q.front();q.pop();         for(int i=0;i<4;i++){             node no;             no.x=ne.x+dx[i];             no.y=ne.y+dy[i];             no.step=ne.step;             if(no.x>=0&&no.x<N&&no.y>=0&&no.y<M&&!visit[no.x][no.y]&&a[no.x][no.y]!='#'){                 visit[no.x][no.y]=1;                 ++no.step;                step[no.x][no.y]+=no.step;//考虑到要遍历两次，要记录两次步数之和，故+=                q.push(no);             }         }     } } int main(void){     while(scanf("%d%d",&N,&M)==2){         memset(step,0,sizeof(step));         for(int i=0;i<N;i++)         for(int j=0;j<M;j++){             cin>>a[i][j];             if(a[i][j]=='Y')Yi.x=i,Yi.y=j,Yi.step=0;             if(a[i][j]=='M')Mer.x=i,Mer.y=j,Mer.step=0;             }         s.x=Yi.x,s.y=Yi.y,s.step=0;         bfs();         s.x=Mer.x,s.y=Mer.y,s.step=0;         bfs();         int res=INF;         for(int i=0;i<N;++i)         for(int j=0;j<M;++j){            // printf("step[%d][%d]=%d\n",i,j,step[i][j]);             if(a[i][j]=='@'&&step[i][j])res=min(res,step[i][j]);//如果有KFC并且step[i][j]被访问过，因为可能村在到不了的KFC这种情况。         }         printf("%d\n",res*11);     } }