诡异的楼梯

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 6570 Accepted Submission(s): 1547

Problem Description

Hogwarts正式开学当前,Harry发明在Hogwarts里,某些楼梯并非静止不动的，相反,他们每隔一分钟就变化一次方向.

比如下面的例子里,一开始楼梯在竖直方向,一分钟当前它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发明对他来说很难找到能使得他最快到达目的地的线路,这时Ron(Harry最好的友人)告诉Harry正好有一个魔法道具可以帮助他寻找这样的线路,而那个魔法道具上的咒语,恰是由你纂写的.

Input

测试数据有多组，每组的表述如下：

第一行有两个数,M和N,接下来是一个M行N列的舆图,'*'表现障碍物,'.'表现走廊,'|'或者'-'表现一个楼梯,并且标明白它在一开始时所处的位置:'|'表现的楼梯在最开始是竖直方向,'-'表现的楼梯在一开始是水平方向.舆图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,舆图中不会涌现两个相连的梯子.Harry每秒只能停顿在'.'或'S'和'T'所标记的格子内.

Output

只有一行,包含一个数T,表现到达目标的最短时间.

注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停顿.并且每次楼梯都恰好在Harry移动完毕当前才改变方向.

Sample Input

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

Sample Output

      7 
Hint
 Hint 
 舆图如下： 

Source

Recommend

JGShining

飞机票：

思绪：模拟 BFS

注意楼梯用过了1遍之后还可以再用因为用来横着走之后还可以竖着走所以不标记楼梯是否走过

一开始没斟酌这里 wa了一次修改了之后直接过了发明做题的时候脑子要苏醒才行这样才能快狠准

每日一道理

风，那么轻柔，带动着小树、小草一起翩翩起舞，当一阵清风飘来，如同母亲的手轻轻抚摸自己的脸庞，我喜欢那种感觉，带有丝丝凉意，让人心旷神怡。享受生活，不一定要有山珍海味、菱罗绸缎为伴，大自然便是上帝所赐予人类最为珍贵的。

代码有点长 by hnust_xiehonghao

#include
     
      #include
      
       #include
       
        using namespace std;char map[30][30];int vis[30][30];int sx,sy,ex,ey,n,m;struct haha{	int x;	int y;	int step;	friend bool operator<(haha a,haha b)	{	    return a.step>b.step;	}}q,temp;int dir[4][2]={1,0,-1,0,0,1,0,-1};bool can(int xx,int yy){	if(xx>=0&&xx
        
         =0&&yy
         
          que;	q.x=sx;	q.y=sy;	q.step=0;	que.push(q);	memset(vis,0,sizeof(vis));	vis[sx][sy]=1;	while(!que.empty())	{		temp=que.top();		que.pop();		if(temp.x==ex&&temp.y==ey) return temp.step;		for(i=0;i<4;i++)		{			int xx;int yy;			xx=temp.x+dir[i][0];			yy=temp.y+dir[i][1];			if(can(xx,yy))			{				if(map[xx][yy]=='|')//如果初始状态为|				{					if(temp.step%2==0)//如果已走了step步 为偶数步 则状态稳定					{						if(can(xx+dir[i][0],yy+dir[i][1]))//方向稳定穿越楼梯看是否能走						{							q.x=xx+dir[i][0];							q.y=yy+dir[i][1];							vis[q.x][q.y]=1;							if((i==1||i==0))//0,1对应的是竖着走 因此直接走 所以加1							{								q.step=temp.step+1;								que.push(q);							}							else//2 3 对应横着走  由于是状态稳定 所以要等到它变成-后再走 所以加2							{								q.step=temp.step+2;								que.push(q);							}						}					}					else					{						if(can(xx+dir[i][0],yy+dir[i][1]))						{							q.x=xx+dir[i][0];							q.y=yy+dir[i][1];							vis[q.x][q.y]=1;							if((i==1||i==0))							{								q.step=temp.step+2;								que.push(q);							}							else							{								q.step=temp.step+1;								que.push(q);							}						}					}				}				else  if(map[xx][yy]=='-')				{					if(temp.step%2==0)					{						if(can(xx+dir[i][0],yy+dir[i][1]))						{							q.x=xx+dir[i][0];							q.y=yy+dir[i][1];							vis[q.x][q.y]=1;							if((i==1||i==0))							{								q.step=temp.step+2;								que.push(q);							}							else							{								q.step=temp.step+1;								que.push(q);							}						}					}					else					{						if(can(xx+dir[i][0],yy+dir[i][1]))						{							q.x=xx+dir[i][0];							q.y=yy+dir[i][1];							vis[q.x][q.y]=1;							if((i==1||i==0))							{                                   								q.step=temp.step+1;								que.push(q);							}							else							{								q.step=temp.step+2;								que.push(q);							}						}					}				}				else                {				vis[xx][yy]=1;				/*注意楼梯用过了1遍之后还可以再用 因为用来横着走之后还可以竖着走 所以不标记楼梯是否走过*/				q.x=xx;				q.y=yy;				q.step=temp.step+1;				que.push(q);				}			}		}	}}int main(){	int i,j;	while(scanf("%d %d",&n,&m)!=EOF)	{		for(i=0;i

文章结束给大家分享下程序员的一些笑话语录：不会，Intel会维持高利润，也会维持竞争局面，国外的竞争不是打死对方的那种。你看日本有尼康，佳能，索尼，都做相机，大家都过得很滋润。别看一堆厂，其实真正控制的是后面的那几个财团——有些竞争对手，后面其实是一家人。

--------------------------------- 原创文章 By

方向和搜索

---------------------------------

转载地址：http://ystsa.baihongyu.com/

你可能感兴趣的文章