Poj 2251 Dungeon Master
2741 ワード
起点から終点までの最短時間の出力を要求する3次元空間の地獄を与える.移動するたびに1分かかります.
考え方:BFSは、2次元空間を3次元空間に拡張するだけで、方向は元の4つから6つ増加しただけです.
考え方:BFSは、2次元空間を3次元空間に拡張するだけで、方向は元の4つから6つ増加しただけです.
#include <iostream>
using namespace std;
#include <deque>
#include <stdio.h>
int map[40][40][40];
int flag[40][40][40];
int l,r,c;
int s1,s2,s3,e1,e2,e3;
deque<int> dem1,dem2,dem3;
int BFS() {
int i,j,k,ctr,size;
int x,y,z,sign;
ctr=0;
x=s1;
y=s2;
z=s3;
sign=0;
flag[x][y][z]=1;
dem1.push_back(x);
dem2.push_back(y);
dem3.push_back(z);
while (!dem1.empty()) {
size=dem1.size();
while (size--) {
x=dem1.front();
dem1.pop_front();
y=dem2.front();
dem2.pop_front();
z=dem3.front();
dem3.pop_front();
if (x==e1&&y==e2&&z==e3) {
sign=1;
break;
}
if (x-1>=1&&map[x-1][y][z]=='.'&&flag[x-1][y][z]==0) {
flag[x-1][y][z]=1;
dem1.push_back(x-1);
dem2.push_back(y);
dem3.push_back(z);
}
if (x+1<=l&&map[x+1][y][z]=='.'&&flag[x+1][y][z]==0) {
flag[x+1][y][z]=1;
dem1.push_back(x+1);
dem2.push_back(y);
dem3.push_back(z);
}
if (y-1>=1&&map[x][y-1][z]=='.'&&flag[x][y-1][z]==0) {
flag[x][y-1][z]=1;
dem1.push_back(x);
dem2.push_back(y-1);
dem3.push_back(z);
}
if (y+1<=r&&map[x][y+1][z]=='.'&&flag[x][y+1][z]==0) {
flag[x][y+1][z]=1;
dem1.push_back(x);
dem2.push_back(y+1);
dem3.push_back(z);
}
if (z-1>=1&&map[x][y][z-1]=='.'&&flag[x][y][z-1]==0) {
flag[x][y][z-1]=1;
dem1.push_back(x);
dem2.push_back(y);
dem3.push_back(z-1);
}
if (z+1<=c&&map[x][y][z+1]=='.'&&flag[x][y][z+1]==0) {
flag[x][y][z+1]=1;
dem1.push_back(x);
dem2.push_back(y);
dem3.push_back(z+1);
}
}
if (sign==1)
break;
ctr++;
}
if (sign==1)
return ctr;
else
return 0;
}
int main()
{
int i,j,k;
int result;
scanf("%d%d%d",&l,&r,&c);
while (!(l==0&&r==0&&c==0)) {
getchar();
for (i=1;i<=l;i++) {
for (j=1;j<=r;j++) {
for (k=1;k<=c;k++) {
flag[i][j][k]=0;
scanf("%c",&map[i][j][k]);
if (map[i][j][k]=='S') {
s1=i;
s2=j;
s3=k;
}
if (map[i][j][k]=='E') {
e1=i;
e2=j;
e3=k;
map[i][j][k]='.';
}
}
getchar();
}
getchar();
}
result=BFS();
dem1.clear();
dem2.clear();
dem3.clear();
if (result==0)
printf("Trapped!
");
else
printf("Escaped in %d minute(s).
",result);
scanf("%d%d%d",&l,&r,&c);
}
return 0;
}