题目描述
bfs模板题的3d版本,用结构体代替PII即可
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 35;
int l, r, c;
char g[N][N][N];
int sx, sy, sz;
int ex, ey, ez;
int st[N][N][N];
typedef struct {
int x, y, z;
} P;
P s, e;
int dx[] = {1, -1, 0, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0, 0};
int dz[] = {0, 0, 0, 0, 0, 1, -1};
bool check(int x, int y, int z)
{
if(x < 0 || x >= l || y < 0 || y >= r || z < 0 || z >= c) return 0;
if(st[x][y][z] != -1) return 0;
if(g[x][y][z] == '#') return 0;
return 1;
}
void bfs()
{
queue<P> q;
q.push(s);
st[s.x][s.y][s.z] = 0;
while(q.size())
{
P t = q.front();
q.pop();
for(int i = 0; i < 8; i++)
{
P m;
m.x = t.x + dx[i];
m.y = t.y + dy[i];
m.z = t.z + dz[i];
if(check(m.x, m.y, m.z))
{
q.push(m);
st[m.x][m.y][m.z] = st[t.x][t.y][t.z] + 1;
}
}
}
}
int main()
{
while(true)
{
memset(st, -1, sizeof st);
cin >> l >> r >> c;
if(!l && !r && !c) break;
for(int i = 0; i < l; i++)
for(int j = 0; j < r; j++)
for(int k = 0; k < c; k++)
{
cin >> g[i][j][k];
if(g[i][j][k] == 'S') s.x = i, s.y = j, s.z = k;
if(g[i][j][k] == 'E') e.x = i, e.y = j, e.z = k;
}
bfs();
if(st[e.x][e.y][e.z] == -1) cout << "Trapped!" << endl;
else
cout << "Escaped in " << st[e.x][e.y][e.z] << " minute(s)." << endl;
}
return 0;
}
tql,明天坐牢辣
tql,球队坐大牢辣