Posted in BFS, Kuangbin

POJ 2251 Dungeon Master/ kuangbin 1B

10/13/2017
Problem: http://poj.org/problem?id=2251
Solution: A plain bfs searching. Only changing 2D to 3D, but the usage is the strategy is the same.


#include<iostream>
#include<string.h>
#include<cstring>
#include<queue>
using namespace std;

int x, y, z;
int xs, ys, zs, xe, ye, ze;
int step = 0;
char map[35][35][35];
bool v[35][35][35];

int dx[10] = {1, 0, 0, -1, 0, 0}; 
int dy[10] = {0, 1, 0, 0, -1, 0}; 
int dz[10] = {0, 0, 1, 0, 0, -1}; 

struct node{
	int time;
	int x, y, z;
	node(int tt, int xx, int yy, int zz) {
		time = tt;
		x = xx;
		y = yy;
		z = zz;
	}
};

bool inrange(int xx, int yy, int zz) {
	return (xx >= 0 && yy >= 0 && zz >= 0 && xx < x && yy < y && zz < z);
}

bool bfs() {
	queue<node> q;
	q.push(node(0, xs, ys, zs));
	v[xs][ys][zs] = true;
	while (!q.empty()) {
		node curr = q.front();
		q.pop();
		if (curr.x == xe && curr.y == ye && curr.z == ze) {
			step = curr.time;
			return true;
		} else {
			for (int i = 0; i < 6; i++) {
				int xx = curr.x + dx[i];
				int yy = curr.y + dy[i];
				int zz = curr.z + dz[i];
				if (inrange(xx, yy, zz) && (map[xx][yy][zz] == '.' || map[xx][yy][zz] == 'E') && !v[xx][yy][zz]) {
					q.push(node(curr.time + 1, xx, yy, zz));
					v[xx][yy][zz] = true;
				}
			}
		}
	}
	return false;
}

int main() {
	while (cin >> x >> y >> z) {
		if (x == 0 && y == 0 && z == 0) {
			return 0;
		}
		memset(map, 0, sizeof(map));
		memset(v, 0, sizeof(v));
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				cin >> map[i][j];
				for (int k = 0; k < z; k++) {
					if (map[i][j][k] == 'S') {
						xs = i;
						ys = j;
						zs = k;
					} else if (map[i][j][k] == 'E') {
						xe = i;
						ye = j;
						ze = k;
					}
				}
			}
		}
		if (bfs()) {
			cout << "Escaped in " << step << " minute(s).";
		} else {
			cout << "Trapped!";
		}
		cout << endl;
	}
	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s