HDU1180 诡异的楼梯（bfs）[C,C++]

题目及翻译

题面

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.

输入

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

输出

只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.

输入样例

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

输出样例

7

提示

样例地图如下

题目思路

一题简单bfs，但是有一个小难点在于楼梯怎么走
题目告知了不会在楼梯上停留
但是事实上你碰到错误方向的楼梯，可以在原地停留等楼梯改变方向
搞清楚这一点，写起来就不难了，但是我没搞清楚的时候wa了20+发
有很多种判断方向的方式，我这里是先记录每个梯子与时间奇偶性的4种可能
‘-’ 与 偶数时间 = '|'与奇数时间 = 横向移动
‘-’ 与 奇数时间 = '|'与偶数时间 = 竖向移动
把横向移动标记为1 竖向移动标记为2，看清楚自己写的移动位置对应的方向，对应着判断即可

注意事项

不能在楼梯上停留，方向错了原地等待
过楼梯之后的地方要重新检查是否能走
楼梯本身不能被标记走过，因为可能重复利用

AC代码

C/C++(几乎没有代码变更)

用时31MS 内存1256K 长度2235B

#include<cstdio>
#include<cstring>//memset所需
#include<queue>//队列
using namespace std;
struct node {int x,y,step;//记录当前坐标和时间node(int x = 0,int y = 0,int step = 0)//构造函数方便使用:x(x),y(y),step(step) {}
};
int n,m;
int step[4][2] = {//改变方向{-1,0},//上{1,0},//下{0,-1},//左{0,1},//右
}; 
char grid[30][30];//记录地图
int vis[30][30];//记录是否走过
int jump[300][2];//用于记录梯子状态
void init(){//初始化memset(vis,0,sizeof(vis));
}
int check(int x,int y){//检查函数if(x < 0 || x >= n)return 0;if(y < 0 || y >= m)return 0;if(vis[x][y])return 0;return 1;
}
int bfs() {node now,nex;queue<node> que;for(int i=0;i<n;++i){//遍历整个地图for(int j=0;j<m;++j){if(grid[i][j] == '*')vis[i][j] = 1;//直接把墙壁标记为走过，少种次判断else if(grid[i][j] == 'S')now = node(i,j);//记录起点}}vis[now.x][now.y] = 1;//起点设置为走过que.push(now);while(!que.empty()){now = que.front();que.pop();if(grid[now.x][now.y] == 'T')return now.step;//到达终点就返回当前步数for(int i=0;i<4;++i){nex.x = now.x + step[i][0];//往当前方向走一步nex.y = now.y + step[i][1];//往当前方向走一步nex.step = now.step;//先获取当前步数用来判断if(!check(nex.x,nex.y))continue;//如果不能走就跳过int flag = jump[grid[nex.x][nex.y]][nex.step&1];//用当前格子和时间的奇偶来判断梯子方向if(flag){//如果flag大于0意味着当前站在梯子上if((flag == 1 && i >= 2 ) || (flag == 2 && i <= 1)){//如果与梯子方向相同nex.x += step[i][0];//继续往前走一步nex.y += step[i][1];//继续往前走一步if(!check(nex.x,nex.y))continue;//如果梯子后不能走就跳过}else nex = now;//如果与梯子方向不同，就原地等待}vis[nex.x][nex.y] = 1;//标记此次目的地被走过nex.step += 1;//时间增加que.push(nex);//入队}}return 0;//如果走不到别忘了返回一个0
}
int main() {jump['-'][0] = jump['|'][1] = 1;//'-' 与 偶数时间 = '|'与奇数时间 = 横向移动jump['-'][1] = jump['|'][0] = 2;//'-' 与 奇数时间 = '|'与偶数时间 = 竖向移动while(~scanf("%d %d",&n,&m)){//循环输入到文件尾init();//初始化for(int i=0;i<n;++i)scanf("%s",grid[i]);//输入地图printf("%d\n",bfs());//输出bfs答案}return 0;
}

本文作者 CSDN@扶她小藜
个人主页链接 https://blog.csdn.net/weixin_44579869