中北大学NUC2017新生赛1003/NOJ-1983

2019-04-14 12:26发布

站内文章 / 模拟电子
11720 0 1381
题意：

一个愉快的周末

时间限制: 1000ms 内存限制: 65535KB

通过次数: 13 总提交次数: 56

问题描述 大家都知道，AiR_H和zbt是好朋友。AiR_H十分喜欢研究历史，这周末他想去山西一个神秘的地方来学习山西的历史，便想拉上zbt一起去。AiR_H对zbt说：山西，因居太行山之西而得名，简称“晋”，东依太行山，西、南依吕梁山、黄河，北依长城，与河北、河南、陕西、内蒙古等省区为界。介于北纬34°34′—40°44′，东经110°14′—114°33′之间，总面积15.67万平方千米…………zbt一脸懵逼，表示，我去，我去还不行吗。他们来到这个无人管理但是有一套自动开门锁门系统神秘的高楼。正在他们在最高楼观光的时候，发现，还有五分钟就要锁门了。被锁住出不去没饭吃饿死的话他们就要变成历史啦！！！zbt十分惊恐，把这栋楼的地图交给AiR_H，让算法大神AiR_H写个程序估计够不够时间。但是AiR_H此时很慌，所以打电话求助你让你帮他算一算至少需要多少时间才能出去。 输入描述 第一行输入一个整数n，代表这栋楼有多少层。AiR_H和zbt就在最高层。（1 <= n <= 100） 下面依次有n个地图（大小都为5 * 5），第i个地图表示第i楼的物品摆放情况 1楼的物品摆放情况 2楼的物品摆放情况 ……………… n楼的物品摆放情况 说明书： '.'代表可以行走的地方 '#'代表障碍物 '@'代表楼梯 1楼'd'字符代表出口 n楼'a'字符代表AiR_H和zbt的位置 相邻两层楼至少有一个楼梯是相同位置的，代表可以从这个位置上楼或者下楼 每个楼梯只能连接x ~ x+1楼或x ~ x-1楼 移动一格算1步，下楼梯算1步 AiR_H和zbt移动的速度为1步/秒 输入保证至少有一条可以出去的通道。 输出描述 输出一个数字代表AiR_H和zbt离开大楼至少需要多少秒。
样例输入 3 ..@#. #.#.. #...d #.#.. ..##. ..@.. #.#.# #...# ##.## @.... ..... ...#. ..a#. ####. @.... 样例输出 28

思路：比赛一开始就发现了这个非常像kuangbin搜索1里面的BFS，兴奋的一顿乱敲最后只得了10分，心态直接炸穿。 描述里有一句话： “相邻两层楼至少有一个楼梯是相同位置的，代表可以从这个位置上楼或者下楼。每个楼梯只能连接x ~ x+1楼或x ~ x-1楼。”      意思就是楼梯只能连接2层，不能连接3层及以上的楼层。则在搜索的时候，若从第i层走楼梯到了第j层，那么第j层的那个对应的楼梯字符要从‘@’变为‘.’。 此意为i到j层为楼梯，j层的这个位置的楼梯就不会到别的层了。     搜索的顺序是先枚举一层的四个方向，若当前为楼梯，再枚举上下方向。
坑点：绝对想不到的WA点：输入!!!我把ios::sync_with_stdio(false);删掉就A了，鹏飞把getchar（）；删了就A了。（他的原因是noj目前不支持getcha   #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; int n; char mapp[110][10][10]; bool vis[110][10][10]; struct node{ int c; int x; int y; int step; }; int sc,sx,sy; int ec,ex,ey; int dir1x[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}; int dir2[] = {-1, 1}; bool check(int x,int y,int z){ if(y >= 0 && y < 5 && z >= 0 && z < 5 && mapp[x][y][z]!='#'&&!vis[x][y][z]) return true; return false; } int bfs(){ queue Q; node a; node nxt; a.c = n-1 , a.x = sx , a.y = sy; a.step = 0; vis[n-1][sx][sy] = 1; Q.push(a); while (!Q.empty()){ a = Q.front(); Q.pop(); //cout<=0 && nxt.c>n; for(int i = 0 ; i

热门文章