本文主要是介绍POJ 2251 *** Dungeon Master，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:有一个R*C*L的三维数组，从S走到E点，其中‘#’点不可到达，‘.’可到达。如果能够到达E点，那么最少需要多少步，如果不能输出不能。
想法:简单bfs，一开始用dfsTLE了，同时发现：dfs(position m,int step){},其中position为struct position{int x,int y,int z;}，poj的判题系统对于dfs({1,1,1},5)是编译不能通过的。。。
代码如下:
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
#include<sstream>
#include<set>
#include<string>
#include<iterator>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int INF = 0x7fffffff;struct position{int x, y, z;
};
int dir[6][3] = { {0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0} };
int L, R, C, cnt;
position start, goal;
char maze[35][35][35];
int mark[35][35][35];void bfs() {queue<position>path;path.push(start);int flag = 1;while (!path.empty()&&flag) {position now = path.front();path.pop();for (int d = 0; d < 6; ++d) {position temp;temp.x = now.x + dir[d][0], temp.y = now.y + dir[d][1], temp.z = now.z + dir[d][2];if (maze[temp.x][temp.y][temp.z] == 'E') {mark[temp.x][temp.y][temp.z] = mark[now.x][now.y][now.z]+1;flag = 0;break;}if (temp.x > 0 && temp.y > 0 && temp.z > 0 && temp.x <= L&&temp.y <= R&&temp.z <= C&&maze[temp.x][temp.y][temp.z] != '#'&&!mark[temp.x][temp.y][temp.z]) {mark[temp.x][temp.y][temp.z] = mark[now.x][now.y][now.z] + 1;path.push(temp);}}}
}int main(void) {
// freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);while (cin >> L >> R >> C, L || R || C) {for (int i = 1; i <= L; ++i)for (int j = 1; j <= R; ++j)for (int k = 1; k <= C; ++k) {cin >> maze[i][j][k];if (maze[i][j][k] == 'S') { start.x = i, start.y = j, start.z = k;}else if (maze[i][j][k] == 'E') { goal.x = i, goal.y = j, goal.z = k;}}memset(mark, 0, sizeof(mark));bfs();if (mark[goal.x][goal.y][goal.z]== 0)cout << "Trapped!" << endl;else cout << "Escaped in " << mark[goal.x][goal.y][goal.z] << " minute(s)." << endl;}
}这篇关于POJ 2251 *** Dungeon Master的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
