首页 > 代码库 > HDU 1180 (BFS搜索)
HDU 1180 (BFS搜索)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1180
题目大意：迷宫中有一堆楼梯，楼梯横竖变化。这些楼梯在奇数时间会变成相反状态，通过楼梯会顺便到达前进方向的下一个点（跳过楼梯）。
同时可以在原地等待，问到达终点的最少时间。
解题思路：
很有趣的一个题。
还是先BFS，对于一个楼梯，change函数负责计算出走楼梯能够到达的新的X和Y，再判一次是否越界或不可达。
注意，在‘.‘点是可以原地等待的，需要额外Push这个点，这也是这题不会出现走不出迷宫的数据的原因，否则因为出不去迷宫，会不停在一个点BFS。
然后，程序就爆了。
#include "cstdio"#include "string"#include "cstring"#include "iostream"#include "queue"using namespace std;char map[25][25];int n,m,sx,sy,ex,ey,dir[4][2]={-1,0,1,0,0,-1,0,1},vis[25][25];struct status{ int x,y,dep; status(int x,int y,int dep):x(x),y(y),dep(dep) {}};status change(status s,int dir,char c,int dep){ if(dep%2) c=(c==‘|‘?‘-‘:‘|‘); if(c==‘|‘) { if(dir==0) return status(s.x-1,s.y,0); if(dir==1) return status(s.x+1,s.y,0); if(dir==2||dir==3) return status(-1,-1,0); } if(c==‘-‘) { if(dir==0||dir==1) return status(-1,-1,0); if(dir==2) return status(s.x,s.y-1,0); if(dir==3) return status(s.x,s.y+1,0); }}int bfs(int x,int y){ 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||vis[X][Y]||map[X][Y]==‘*‘) continue; if(map[X][Y]==‘|‘||map[X][Y]==‘-‘) { status nw=change(status(X,Y,0),s,map[X][Y],t.dep); X=nw.x;Y=nw.y; } if(X<1||X>n||Y<1||Y>m||vis[X][Y]||map[X][Y]==‘*‘) continue; vis[X][Y]=true; if(X==ex&&Y==ey) return t.dep+1; Q.push(status(X,Y,t.dep+1)); } if(map[t.x][t.y]!=‘|‘||map[t.x][t.y]!=‘-‘) Q.push(status(t.x,t.y,t.dep+1)); } return -1;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>n>>m) { memset(vis,0,sizeof(vis)); 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]==‘S‘) {sx=i;sy=j+1;} if(tt[j]==‘T‘) {ex=i;ey=j+1;} } } int ans=bfs(sx,sy); cout<<ans<<endl; }}
| 11891440 | 2014-10-17 01:13:57 | Accepted | 1180 | 15MS | 308K | 2067 B | C++ | Physcal |
HDU 1180 (BFS搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。