1248:Dungeon Master
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 7238 通过数: 2862
【题目描述】
这题是一个三维的迷宫题目,其中用‘.’表示空地,‘#’表示障碍物,‘S’表示起点,‘E’表示终点,求从起点到终点的最小移动次数,解法和二维的类似,只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动,每次都只能移到相邻的空位,每次需要花费一分钟,求从起点到终点最少要多久。
【输入】
多组测试数据。
一组测试测试数据表示一个三维迷宫:
前三个数,分别表示层数、一个面的长和宽,后面是每层的平面图。前三个数据为三个零表示结束。
【输出】
最小移动次数。
【输入样例】
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
【输出样例】
Escaped in 11 minute(s).
Trapped!
【提示】
对于题目给出数据的含义就是输入l,r,c,分别代表迷宫有l层,每层长宽分别是c,r。对于数据以可以这样移动:
(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->
(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)
共11步就可以到达终点 对于数据二明显不能到达,则输出Trapped!
这题用BFS解,每次去队首元素,如果是终点则输出结果移动的次数,否则,从该点开始分别向东南西北上下移动(如果可以走的话)并继续搜,如果到队列为空还没搜到解法,则说明无解。
#include <iostream> #include <cstring> #include <queue> #include <cstdio> #define MAX 31 using namespace std; char mapMAX[MAX]; int vedMAX[MAX]; int h, a, b; int dx[] = {1, -1, 0, 0, 0, 0}; int dy[] = {0, 0, 1, -1, 0, 0}; int dz[] = {0, 0, 0, 0, 1, -1}; struct point { int x, y, z; int step; }; // ‘.’表示空地,‘#’表示障碍物,‘S’表示起点,‘E’表示终点 inline bool isok(point temp) { if (temp.x < 0 || temp.y < 0 || temp.z < 0) return false; if (temp.x >= a || temp.y >= b || temp.z >= h) return false; if (maptemp.z[temp.y] == '#') return false; if (vedtemp.z[temp.y] <= temp.step) return false; return true; } int main() { while (true) { cin >> h >> a >> b; if (h == 0 && a == 0 && b == 0) return 0; memset(map, 0, sizeof(map)); memset(ved, 0x7f, sizeof(ved)); point start, end; for (int i = 0; i < h; i++) { for (int j = 0; j < a; j++) { for (int k = 0; k < b; k++) { cin >> mapi[k]; //scanf(" %c", &mapi[k]); if (mapi[k] == 'S') start = {j, k, i, 0}; if (mapi[k] == 'E') end = {j, k, i, 0}; } } } queue<point> list; list.push(start); while (!list.empty()) { point temp = list.front(); list.pop(); for (int i = 0; i < sizeof(dx)/sizeof(int); i++) { point next = temp; next.x += dx[i]; next.y += dy[i]; next.z += dz[i]; next.step++; if (!isok(next)) continue; else { list.push(next); vednext.z[next.y] = next.step; } } } if (vedend.z[end.y] == 0x7f7f7f7f) //无解 cout << "Trapped!" << endl; else printf("Escaped in %d minute(s).n", vedend.z[end.y]); } }
Comment here is closed