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;
}