5 5 **..T **.*. ..|.. .*.*. S....
7地图如下: 注意楼梯用过了1遍之后还可以再用 因为用来横着走之后还可以竖着走 所以不标记楼梯是否走过 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<queue> using namespace std; int flag[25][25],sum,x1,z1,dir[4][2]={0,-1,-1,0,0,1,1,0}; char map[25][25]; typedef struct node { int x,y,step,f; }node; queue<node>a; void clear() { while(!a.empty()) a.pop(); } int bfs(int x1,int z1) { node now,next; now.x=x1;now.y=z1;now.step=0;now.f=0; a.push(now); while(!a.empty()) { now=a.front(); a.pop(); if(now.f==1) { now.f=0; a.push(now); continue; } for(int i=0;i<4;i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; next.step=now.step+1; next.f=0; int xx=next.x; int yy=next.y; if(map[xx][yy]==‘*‘||flag[xx][yy]==1) continue; if(map[xx][yy]==‘T‘) return next.step; if(map[xx][yy]==‘|‘) { if((now.step%2==0&&(i==1||i==3))||now.step%2==1&&(i==0||i==2)) { next.x=next.x+dir[i][0]; next.y=next.y+dir[i][1]; if(map[next.x][next.y]==‘*‘||flag[xx][yy]==1) continue; if(map[next.x][next.y]==‘T‘) return next.step; flag[next.x][next.y]=1; a.push(next); } else { next.x=next.x+dir[i][0]; next.y=next.y+dir[i][1]; next.step=next.step+1; next.f=1; if(map[next.x][next.y]==‘*‘||flag[xx][yy]==1) continue; if(map[next.x][next.y]==‘T‘) return next.step; flag[next.x][next.y]=1; a.push(next); } continue; } if(map[xx][yy]==‘-‘) { if((now.step%2==0&&(i==0||i==2))||now.step%2==1&&(i==1||i==3)) { next.x=next.x+dir[i][0]; next.y=next.y+dir[i][1]; if(map[next.x][next.y]==‘T‘) return next.step; if(map[next.x][next.y]==‘*‘||flag[xx][yy]==1) continue; flag[next.x][next.y]=1; a.push(next); } else { next.x=next.x+dir[i][0]; next.y=next.y+dir[i][1]; if(map[next.x][next.y]==‘*‘||flag[xx][yy]==1) continue; next.step=next.step+1; next.f=1; if(map[next.x][next.y]==‘T‘) return next.step; flag[next.x][next.y]=1; a.push(next); } continue; } flag[xx][yy]=1; a.push(next); } } } int main() { int n,m,i,j; while(~scanf("%d%d",&n,&m)) { sum=0; memset(flag,0,sizeof(flag)); memset(map,‘*‘,sizeof(map)); clear(); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>map[i][j]; if(map[i][j]==‘S‘) { x1=i; z1=j; } } flag[x1][z1]=1; sum=bfs(x1,z1); cout<<sum<<endl; } return 0; }HintHint
HDU 1180 诡异的楼梯 (DFS),布布扣,bubuko.com
原文:http://blog.csdn.net/qq2256420822/article/details/38358993