hdu1180 诡异的楼梯 (广搜做着比较有chengjiuga)

本文主要是介绍hdu1180 诡异的楼梯 (广搜做着比较有chengjiuga)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

诡异的楼梯

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 14457 Accepted Submission(s): 3693

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

  7Hint
Hint
 
地图如下：

Source

Gardon-DYGG Contest 1

Recommend

JGShining | We have carefully selected several similar problems for you: 1072 1026 1240 1254 1372

Statistic | Submit | Discuss | Note

写了大概2个小时终于a了

两个小提示：

可能有多个楼梯
楼梯的另一端连接的可能是障碍物或者走廊或者楼梯或者边界

测试数据：

1 5

S|-|T

答案是：4

还有一个就是如何判断当前楼梯的状态

用一个二维数组tz[25][25]记录初始的梯子状态，

如果初始梯子是横着的tz[i][j]=1
如果是竖着的tz[i][j]=0;
如果不是梯子就赋值为tz[i][j]=-1;

另外一个就是走到梯子旁如何判断梯子的方向和当前行走的方向一致

可以用一个二维数组表示当前行走的方向

int dir[4][2]={1,0,0,1,-1,0,0,-1};//下右上左

如果dir[i][j]中i%2==0就是纵向走，i%2==1就是横向走

假设当前状态花费的时间为cost

如果(cost+tz[x][y])%2==0就表示当前楼梯的状态是竖着的否则是横着的

通过计算(cost+tz[x][y])%2和i%2是否相等就对当前的行走做出判断

具体代码如下：

#include <stdio.h> 
#include <queue>
#include <string.h>
using namespace std;
char map[25][25];
int tz[25][25];
bool vis[25][25];
int dir[4][2]={1,0,0,1,-1,0,0,-1};//下 右 上 左 
int n,m;
int s_x,s_y,t_x,t_y;
struct node
{int x,y;int cost;friend bool operator<(node a,node b){return a.cost>b.cost;}
};
bool limit(int x,int y)
{if(x<0||y<0||x==m||y==n||map[x][y]=='*') return false;return true;
}
int bfs()
{priority_queue<node>s;node node1,node2;node1.x=s_x,node1.y=s_y,node1.cost=0;s.push(node1);while(!s.empty()){node1=node2=s.top();s.pop();//	printf("%d %d %d\n",node1.x,node1.y,node1.cost);if(node1.x==t_x&&node1.y==t_y) return node1.cost;if(vis[node1.x][node1.y]) continue;vis[node1.x][node1.y]=true;for(int i=0;i<4;i++){int xx=node1.x+dir[i][0];int yy=node1.y+dir[i][1];if(limit(xx,yy)&&!vis[xx][yy]){if(map[xx][yy]=='t'){	//如果是梯子 	xx+=dir[i][0];yy+=dir[i][1];//如果当前行走的方向和梯子的方向一致 直接走 		if((tz[xx-dir[i][0]][yy-dir[i][1]]+node1.cost)%2==i%2){	//	printf("%怎么啦");			//如果梯子后面连着梯子					while(limit(xx,yy)&&tz[xx][yy]+tz[xx+dir[i][0]][yy+dir[i][1]]==1){xx+=dir[i][0];yy+=dir[i][1];node1.cost++;//	printf("%d %d %d快活啊",xx,yy,node1.cost);}if(map[xx][yy]=='t'){xx+=dir[i][0];yy+=dir[i][1];node1.cost++;}if(map[xx][yy]=='.'||map[xx][yy]=='T'){node1.x=xx;node1.y=yy;node1.cost++;s.push(node1);}}else{//如果当前行走的方向和梯子的方向不一致  时间+2 //	printf("嗯啊");//如果梯子后面连着梯子	while(limit(xx,yy)&&tz[xx][yy]+tz[xx+dir[i][0]][yy+dir[i][1]]==1){xx+=dir[i][0];yy+=dir[i][1];node1.cost++;}if(map[xx][yy]=='t'){xx+=dir[i][0];yy+=dir[i][1];node1.cost++;}if(map[xx][yy]=='.'||map[xx][yy]=='T'){node1.x=xx;node1.y=yy;node1.cost+=2;s.push(node1);}}	}else{node1.x=xx;node1.y=yy;node1.cost++;s.push(node1);} node1=node2;}} }
}
int main()
{//freopen("in.txt","r",stdin);while(~scanf("%d %d",&m,&n)){memset(map,0,sizeof(map));memset(tz,-1,sizeof(tz));memset(vis,false,sizeof(vis));for(int i=0;i<m;i++){getchar();for(int j=0;j<n;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S') s_x=i,s_y=j;if(map[i][j]=='T') t_x=i,t_y=j;if(map[i][j]=='|') map[i][j]='t',tz[i][j]=0;if(map[i][j]=='-') map[i][j]='t',tz[i][j]=1;}}printf("%d\n",bfs());}return 0;
}

这篇关于hdu1180 诡异的楼梯 (广搜做着比较有chengjiuga)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！