UVA532 Dungeon Master(三维BFS)

裸搜索,就摁搜。

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
char mp[31][31][31];
bool vis[31][31][31];
int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};
int l, m, n;
struct node
{
	int x, y, z, t;
};
node s, e;
int ans;
void bfs()
{
	queue<node> q;
	q.push(s);
	vis[s.z][s.x][s.y] = 1;
	while(q.size())
	{
		node now = q.front();
		q.pop();
		if(now.x == e.x && now.y == e.y && now.z == e.z)
		{
			ans = now.t;
			break;
		}
		for(int i = 0; i < 6; i++)
		{
			int nx = now.x + dir[i][0], ny = now.y + dir[i][1], nz = now.z + dir[i][2];
			if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && nz >= 1 && nz <= l && mp[nz][nx][ny] != '#' && !vis[nz][nx][ny])
			{
				node nxt;
				nxt.x = nx, nxt.y = ny, nxt.z = nz, nxt.t = now.t + 1;
				vis[nz][nx][ny] = 1;
				q.push(nxt);
			}
		}
	}
	return;
}
int main()
{
	freopen("data.txt", "r", stdin);
	while(scanf("%d%d%d", &l, &n, &m) && l && m && n)
	{
		ans = 0x3f3f3f3f;
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i <= l; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				scanf("%s", mp[i][j] + 1);
			}
		}
		for(int i = 1; i <= l; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				for(int k = 1; k <= m; k++)
				{
					if(mp[i][j][k] == 'S')
					{
						s.z = i, s.x = j, s.y = k;
						s.t = 0;
					}
					else if(mp[i][j][k] == 'E')
					{
						e.z = i, e.x = j, e.y = k;
					}
				}
			}
		}
		bfs();
		if(ans != 0x3f3f3f3f) cout << "Escaped in " << ans << " minute(s).";
		else cout << "Trapped!";
		cout << endl;
	}
	return 0;
}
上一篇:POJ-2251 Dungeon Master (三维BFS)


下一篇:Spark源码学习1.3——TaskSetManager.scala