首页 > 代码库 > HDU 1242 (BFS搜索+优先队列)
HDU 1242 (BFS搜索+优先队列)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1242
题目大意：多个起点到一个终点，普通点耗时1，特殊点耗时2，求到达终点的最少耗时。
解题思路：
如果没有特殊点，就是普通BFS。
由于特殊点的介入，所以对于一个点，可能由不同种方式到达，所以使用优先队列，对于一个点，最先取出的点用的方式肯定是最优的。
同时使用优先队列也为BFS过程提供一个剪枝，因为最先到达肯定是最优结果，只要搜到第一个结果，后面就不用搜了。
注意有多个起点，所以先记录下所有起点，依次BFS找最小。
#include "cstdio"#include "string"#include "cstring"#include "iostream"#include "vector"#include "queue"using namespace std;#define inf 1<<28struct status{ int x,y,dep; status(int x,int y,int dep):x(x),y(y),dep(dep) {} bool operator < (const status &a) const { return dep>a.dep; }};int n,m,map[205][205],vis[205][205],dir[4][2]={-1,0,1,0,0,-1,0,1},ans;void bfs(int x,int y){ priority_queue<status> Q; Q.push(status(x,y,0)); bool flag=false; while(!Q.empty()) { if(flag) break; status t=Q.top();Q.pop(); vis[t.x][t.y]=true; for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(vis[X][Y]||X<0||X>n||Y<0||Y>n||!map[X][Y]) continue; if(map[X][Y]==2) {flag=true;ans=min(ans,t.dep+1);}; if(map[X][Y]==3) Q.push(status(X,Y,t.dep+2)); else 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&&n) { vector<status> f; ans=inf; for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { if(tt[j]==‘#‘) map[i][j+1]=0; if(tt[j]==‘.‘) map[i][j+1]=1; if(tt[j]==‘a‘) map[i][j+1]=2; if(tt[j]==‘x‘) map[i][j+1]=3; if(tt[j]==‘r‘) {map[i][j+1]=4;f.push_back(status(i,j+1,0));} } } for(int i=0;i<f.size();i++) { memset(vis,0,sizeof(vis)); bfs(f[i].x,f[i].y); } if(ans!=inf) cout<<ans<<endl; else cout<<"Poor ANGEL has to stay in the prison all his life."<<endl; }}
| 11867790 | 2014-10-14 00:53:01 | Accepted | 1242 | 46MS | 644K | 1840 B | C++ | Physcal |
HDU 1242 (BFS搜索+优先队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。