题目链接: http://poj.org/problem?id=1947
题目大意：两人选择图中一个kfc约会。问两人到达时间之和的最小值。
解题思路：
对于一个KFC，两人的BFS目标必须一致。
于是就有以下的SB行为：记录所有KFC，对于每个KFC，对两人BFS。然后你就会看见红红的TLE。
实际上，只需要两次BFS就可以了，用time_k[0][i]记录a同学到达第i个kfc的时间，time_k[1][i]记录b同学到达第i个kfc的时间。
在一次bfs过程中，记录到达所有kfc的时间。
本题有个不严谨的地方，就是没有说明不被选择的kfc是相当于road还是障碍，我是当成road算的。
由于图中有些kfc是不能到达的，所以time_k数组初始化为inf，防止不能到达的kfc扰乱结果。
最后ans=min(ans,time_k[0][i]+time_k[1][i])。
#include "cstdio"
#include "cstring"
#include "string"
#include "iostream"
#include "queue"
#include "vector"
using namespace std;
#define inf 0x3f3f3f3f
int n,m,sx,sy,ssx,ssy,ex,ey,dir[][]={-,,,,,-,,},vis[][],ans,cnt,kfc[][],time_k[][*];
char map[][];
struct status
{
int x,y,dep;
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
};
void bfs(int x,int y,int p)
{
memset(vis,,sizeof(vis));
queue<status> Q;
Q.push(status(x,y,));
vis[x][y]=true;
while(!Q.empty())
{
status t=Q.front();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(X<||X>n||Y<||Y>m||map[X][Y]=='#'||vis[X][Y]) continue;
vis[X][Y]=true;
if(map[X][Y]=='@') time_k[p][kfc[X][Y]]=t.dep+;
Q.push(status(X,Y,t.dep+));
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m)
{
memset(time_k,0x3f,sizeof(time_k));
ans=inf,cnt=;
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
map[i][j+]=tt[j];
if(tt[j]=='Y') {sx=i;sy=j+;}
if(tt[j]=='M') {ssx=i;ssy=j+;}
if(tt[j]=='@') {kfc[i][j+]=++cnt;}
}
}
bfs(sx,sy,);bfs(ssx,ssy,);
for(int i=;i<=cnt;i++) ans=min(ans,(time_k[][i]+time_k[][i])*);
cout<<ans<<endl;
}
}
| 11915289 | 2014-10-19 20:15:30 | Accepted | 2612 | 15MS | 996K | 1596 B | C++ | Physcal |