本题与1101. 献给阿尔吉侬的花束基本一样,只不过是从二维变成了三维。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
char g[N][N][N];
struct Point
{
int x,y,z;
};
int dist[N][N][N];
int l,r,c;
int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};
int bfs(Point start,Point end)
{
queue<Point> q;
q.push(start);
memset(dist,-1,sizeof dist);
dist[start.x][start.y][start.z] = 0;
while(q.size())
{
Point t = q.front();
q.pop();
for(int i = 0;i < 6;i++)
{
int x = t.x + dx[i];
int y = t.y + dy[i];
int z = t.z + dz[i];
if(x < 0 || x >= l || y < 0 || y >= r || z < 0 || z >= c) continue;
if(g[x][y][z] == '#') continue;
if(dist[x][y][z] != -1) continue;
dist[x][y][z] = dist[t.x][t.y][t.z] + 1;
if(end.x == x && end.y == y && end.z == z) return dist[x][y][z];
q.push({x,y,z});
}
}
return -1;
}
int main()
{
while(cin >> l >> r >> c ,l || r || c)
{
Point start,end;
for(int i = 0;i < l;i++)
{
for(int j = 0;j < r;j++)
{
cin >> g[i][j];
for(int k = 0;k < c;k++)
{
char t = g[i][j][k];
if(t == 'S')
{
start = {i,j,k};
}
else if(t == 'E')
{
end = {i,j,k};
}
}
}
}
int distance = bfs(start,end);
if(distance == -1)
{
puts("Trapped!");
}
else
{
cout << "Escaped in " << distance << " minute(s)." << endl;
}
}
return 0;
}
下面是不用queue来写
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 110;
char g[N][N][N];
struct Point
{
int x,y,z;
};
int dist[N][N][N];
Point q[N * N * N];
int l,r,c;
int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};
int bfs(Point start,Point end)
{
int hh = 0,tt = 0;
q[0] = start;
memset(dist,-1,sizeof dist);
dist[start.x][start.y][start.z] = 0;
while(hh <= tt)
{
Point t = q[hh++];
for(int i = 0;i < 6;i++)
{
int x = t.x + dx[i];
int y = t.y + dy[i];
int z = t.z + dz[i];
if(x < 0 || x >= l || y < 0 || y >= r || z < 0 || z >= c) continue;
if(g[x][y][z] == '#') continue;
if(dist[x][y][z] != -1) continue;
dist[x][y][z] = dist[t.x][t.y][t.z] + 1;
if(end.x == x && end.y == y && end.z == z) return dist[x][y][z];
q[++tt] = {x,y,z};
}
}
return -1;
}
int main()
{
while(cin >> l >> r >> c ,l || r || c)
{
Point start,end;
for(int i = 0;i < l;i++)
{
for(int j = 0;j < r;j++)
{
cin >> g[i][j];
for(int k = 0;k < c;k++)
{
char t = g[i][j][k];
if(t == 'S')
{
start = {i,j,k};
}
else if(t == 'E')
{
end = {i,j,k};
}
}
}
}
int distance = bfs(start,end);
if(distance == -1)
{
puts("Trapped!");
}
else
{
cout << "Escaped in " << distance << " minute(s)." << endl;
}
}
return 0;
}