c124: 00532 - Dungeon Master

解題心得

除了東西南北外，多考慮上下的bfs。

程式碼

#include <iostream>
#include <queue>
using namespace std;

struct Point
{
	int level, x, y, step = -1;
};
int l, r, c;
char map[31][31][31];


int main()
{
	
	while (cin >> l >> r >> c)
	{
		if (l == 0 && r == 0 && c == 0) break;

		bool isVisit[31][31][31] = { false };
		Point start, end, now;
		for (int i = 0; i < l; i++)
		{
			for (int j = 0; j < r; j++)
			{
				for (int k = 0; k < c; k++)
				{
					cin >> map[i][j][k];
					if (map[i][j][k] == 'S')
						start.level = i, start.x = j, start.y = k;
					if (map[i][j][k] == 'E')
						end.level = i, end.x = j, end.y = k;
				}
			}
			cin.ignore();
		}
		
		queue<Point> q;
		start.step = 0;
		q.push(start);
		isVisit[start.level][start.x][start.y] = true;
		bool isValid = false;
		while (!q.empty())
		{
			now = q.front(); q.pop();
			//cout << now.level << " " << now.x << " " << now.y << " " << now.step << endl;
			if (map[now.level][now.x][now.y] == 'E')
			{
				cout << "Escaped in " << now.step << " minute(s)." << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.level][now.x - 1][now.y] != '#' && !isVisit[now.level][now.x - 1][now.y])
			{
				isVisit[now.level][now.x - 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x - 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < r && map[now.level][now.x + 1][now.y] != '#' && !isVisit[now.level][now.x + 1][now.y])
			{
				isVisit[now.level][now.x + 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x + 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.level][now.x][now.y - 1] != '#' && !isVisit[now.level][now.x][now.y - 1])
			{
				isVisit[now.level][now.x][now.y - 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y - 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < c && map[now.level][now.x][now.y + 1] != '#' && !isVisit[now.level][now.x][now.y + 1])
			{
				isVisit[now.level][now.x][now.y + 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y + 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level - 1 >= 0 && map[now.level - 1][now.x][now.y] != '#' && !isVisit[now.level - 1][now.x][now.y])
			{
				isVisit[now.level- 1][now.x][now.y ] = true;
				Point p; p.level = now.level - 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level + 1 < l && map[now.level + 1][now.x][now.y] != '#' && !isVisit[now.level + 1][now.x][now.y])
			{
				isVisit[now.level + 1][now.x][now.y] = true;
				Point p; p.level = now.level + 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisit[now.level][now.x][now.y] = true;
		}
		if (!isValid) cout << "Trapped!" << endl;
	}
	return 0;
}