首页 > 代码库 > hdu1180诡异的楼梯……bfs走迷宫……wa了16次,我太渣了
hdu1180诡异的楼梯……bfs走迷宫……wa了16次,我太渣了
#include<iostream> #include<queue> #include<cstring> using namespace std; int row,line,xx[4]={-1,1,0,0},yy[4]={0,0,-1,1}; char map[100][100]; bool vis[100][100]; struct node { int x,y,step; }st; void init() { int i,j; bool flag=1; for(i=0;i<row;i++) scanf("%s",map[i]); for(i=0;flag&&i<row;i++) for(j=0;flag&&j<line;j++) if(map[i][j]=='S') { st.x=i; st.y=j; st.step=0; flag=0; } memset(vis,0,sizeof(vis)); vis[st.x][st.y]=1; } bool iscan(int x,int y) { if(x<0||y<0||x>=row||y>=line||vis[x][y]||map[x][y]=='*') return 0; return 1; } void bfs() { int i; queue<node>qq; node t1,t2; qq.push(st); while(qq.size()) { t1=qq.front(); qq.pop(); if(map[t1.x][t1.y]=='T') { printf("%d\n",t1.step); return; } for(i=0;i<4;i++) { t2=t1; t2.x+=xx[i]; t2.y+=yy[i]; t2.step++; if(!iscan(t2.x,t2.y)) continue; if(map[t2.x][t2.y]=='.'||map[t2.x][t2.y]=='T') { vis[t2.x][t2.y]=1; qq.push(t2); } else if((map[t2.x][t2.y]=='|'&&!(t1.step&1))||(map[t2.x][t2.y]=='-'&&(t1.step&1))) { if(i>1) { t2=t1; t2.step++; qq.push(t2); continue; } t2.x+=xx[i]; if(!iscan(t2.x,t2.y)) continue; vis[t2.x][t2.y]=1; qq.push(t2); } else { if(i<2) { t2=t1; t2.step++; qq.push(t2); continue; } t2.y+=yy[i]; if(!iscan(t2.x,t2.y)) continue; vis[t2.x][t2.y]=1; qq.push(t2); } } } } int main() { while(scanf("%d%d",&row,&line)!=EOF) { init(); bfs(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。