首页 > 代码库 > HDU 2612 (BFS搜索+多终点)
HDU 2612 (BFS搜索+多终点)
题目链接: 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 0x3f3f3f3fint n,m,sx,sy,ssx,ssy,ex,ey,dir[4][2]={-1,0,1,0,0,-1,0,1},vis[205][205],ans,cnt,kfc[205][205],time_k[2][205*205];char map[205][205];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,0,sizeof(vis)); queue<status> Q; Q.push(status(x,y,0)); vis[x][y]=true; while(!Q.empty()) { status t=Q.front();Q.pop(); for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(X<1||X>n||Y<1||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+1; Q.push(status(X,Y,t.dep+1)); } }}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=0; for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { map[i][j+1]=tt[j]; if(tt[j]==‘Y‘) {sx=i;sy=j+1;} if(tt[j]==‘M‘) {ssx=i;ssy=j+1;} if(tt[j]==‘@‘) {kfc[i][j+1]=++cnt;} } } bfs(sx,sy,0);bfs(ssx,ssy,1); for(int i=1;i<=cnt;i++) ans=min(ans,(time_k[0][i]+time_k[1][i])*11); cout<<ans<<endl; }}
| 11915289 | 2014-10-19 20:15:30 | Accepted | 2612 | 15MS | 996K | 1596 B | C++ | Physcal |
HDU 2612 (BFS搜索+多终点)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。