?

诡异的楼梯

5 5
**..T
**.*.
..|..
.*.*.
S....

7

HintHint 
地图如下：

?

?

开始wa了很多次，原来是题意没搞清，还以为只有例子中' |' 这一种楼梯的符号，原来还有’-‘！

要点： 优先队列的构造，判断条件的抽取，特殊条件（等待一秒在前进）

优先队列，使得当前时间小的先出队列，

所以当前坐标的结构体需要这样写

?

struct node{
	int x,y,step; 
        //两种方式重载小于号
	/* friend bool operator <(node a,node b){
		return a.step>b.step;
	} */
	bool operator <(const node &a)const{
		return step>a.step;//步数小的先出队列
	}
}init;

?

所以用statue[][]这个数组储存走过位置的当前步数；

判断条件很多，我们把它抽取到函数judge

?

bool judge(node no){
?? ?//如果超出边界，或者该位置是墙，或者当前步数大于之前步数,返回false
?? ?if(no.x<0||no.x>=n||no.y<0||no.y>=m||map[no.x][no.y]=='*'||(statue[no.x][no.y]&&no.step>=statue[no.x][no.y]))
?? ??? ?return false;
?? ?return true;
}

?

将这个情况与 一致时的情况放在一起，只是步数不同

【源代码】

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int n,m; const int maxn = 21; int stx,sty,gx,gy; char map[maxn][maxn]; bool vis[maxn][maxn]; int statue[maxn][maxn]; int dx[4]={0,0,1,-1}; int dy[4]={-1,1,0,0}; struct node{ int x,y,step; /* friend bool operator <(node a,node b){ return a.step>b.step; } */ bool operator <(const node &a)const{ return step>a.step;//步数小的先出队列 } }init; bool judge(node no){ //如果超出边界，或者该位置是墙，或者当前步数大于之前步数,返回false if(no.x<0||no.x>=n||no.y<0||no.y>=m||map[no.x][no.y]=='*'||(statue[no.x][no.y]&&no.step>=statue[no.x][no.y])) return false; return true; } int bfs(){ init.x=stx;init.y=sty;init.step=0; statue[init.x][init.y]=1; priority_queue
     
      pq; while(!pq.empty()) pq.pop(); pq.push(init); while(!pq.empty()){ node past=pq.top(); node now; pq.pop(); for(int i=0;i<4;i++){ now.x=past.x+dx[i]; now.y=past.y+dy[i]; now.step=past.step+1; if(!judge(now)) continue; if(map[now.x][now.y]=='|'){ if(now.x==past.x&&(past.step & 1)==0) //当横着走，且 | 不变 now.step++; if(now.y==past.y&&(past.step & 1)==1)//当 竖着走 且 |变 { now.step++; } now.x+=dx[i]; now.y+=dy[i]; } else if(map[now.x][now.y]=='-'){ if(now.x==past.x&&(past.step & 1)==1) //当横着走，且 -变 now.step++; if(now.y==past.y&&(past.step & 1)==0)//当竖着走 且-不变 now.step++; now.x+=dx[i]; now.y+=dy[i]; } if(!judge(now)) continue; if(map[now.x][now.y]=='T') return now.step; statue[now.x][now.y]=now.step; pq.push(now); } } return 0; } int main(){ while(cin>>n>>m){ for(int i=0;i
      
       >map[i][j]; if(map[i][j]=='S') stx=i,sty=j; if(map[i][j]=='T') gx=i,gy=j; } memset(statue,0,sizeof(statue)); int ans=bfs(); cout<
       
        
?
        
?
        
?