三维迷宫问题——Acwing1096. 地牢大师
题目
你现在被困在一个三维地牢中，需要找到最快脱离的出路！
地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。
向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。
你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。
请问，你有可能逃脱吗？
如果可以，需要多长时间？
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 L,R,CL,R,C 分别表示地牢层数，以及每一层地牢的行数和列数。
接下来是 LL 个 RR 行 CC 列的字符矩阵，用来表示每一层地牢的具体状况。
每个字符用来描述一个地牢单元的具体状况。
其中, 充满岩石障碍的单元格用”#”表示，不含障碍的空单元格用”.”表示，你的起始位置用”S”表示，终点用”E”表示。
每一个字符矩阵后面都会包含一个空行。
当输入一行为”0 0 0”时，表示输入终止。
输出格式
每组数据输出一个结果，每个结果占一行。
如果能够逃脱地牢，则输出”Escaped in x minute(s).”，其中X为逃脱所需最短时间。
如果不能逃脱地牢，则输出”Trapped!”。
数据范围
1≤L,R,C≤1001≤L,R,C≤100
输入样例：
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
输出样例：
Escaped in 11 minute(s).
Trapped!
c++题解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 105,INF = 0x3f3f3f3f;
int dx[6] = {0, 1, 0, -1, 0, 0}; //东南西北上下
int dy[6] = {1, 0, -1, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int dis[N][N][N];
char g[N][N][N];
int l,r,c;
struct Point{
int x,y,z;
};
void bfs(Point start, Point end) {
queue<Point> q;
q.push(start);
memset(dis, -1, sizeof dis);
dis[start.x][start.y][start.z] = 0;
while (!q.empty()) {
Point t = q.front();
q.pop();
for (int i = 0; i < 6; i++) {
int x = t.x + dx[i], y = t.y + dy[i], z = t.z + dz[i];
if (x < 0 || x >= l || y < 0 || y >= r || z < 0 || z >= c||dis[x][y][z]!=-1||g[x][y][z]=='#') {
continue;
}
dis[x][y][z] = dis[t.x][t.y][t.z] + 1;
q.push({x, y, z});
}
}
if(dis[end.x][end.y][end.z]==-1){
cout <<"Trapped!" <<endl;
}else{
cout << "Escaped in " <<dis[end.x][end.y][end.z]<<" minute(s)."<<endl;
}
}
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++) {
scanf("%s", 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};
}
}
}
}
bfs(start,end);
}
}
Java题解
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
class PIIs{
public int x;//第x层
public int y;//第y行
public int z;//第z列
public PIIs(int x,int y,int z)
{
this.x = x;
this.y = y;
this.z = z;
}
}
static int N = 110;
static int L;
static int R;
static int C;
static PIIs start;
static PIIs end;
static char[][][] g = new char[N][N][N];
static int[][][] dist = new int[N][N][N];
static int[] dx = new int[] {1,-1,0,0,0,0};
static int[] dy = new int[] {0,0,1,-1,0,0};
static int[] dz = new int[] {0,0,0,0,1,-1};
static int bfs()
{
Queue<PIIs> q = new LinkedList<PIIs>();
q.add(start);
for(int i = 0;i < L;i++)
for(int j = 0;j < R;j++)
Arrays.fill(dist[i][j], -1);
dist[start.x][start.y][start.z] = 0;
while(!q.isEmpty())
{
PIIs t = q.poll();
for(int i = 0;i < 6;i++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
int c = t.z + dz[i];
if(a < 0 || a >= L || b < 0 || b >= R || c < 0 || c >= C) continue;
if(g[a][b][c] == '#') continue;
if(dist[a][b][c] != -1) continue;
dist[a][b][c] = dist[t.x][t.y][t.z] + 1;
if(a == end.x && b == end.y && c == end.z) return dist[a][b][c];
q.add(new PIIs(a,b,c));
}
}
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext())
{
L = scan.nextInt();
R = scan.nextInt();
C = scan.nextInt();
if(L == 0 && R == 0 && C == 0) break;
for(int i = 0;i < L;i ++)
{
for(int j = 0;j < R;j ++)
{
char[] charArray = scan.next().toCharArray();
for(int k = 0;k < C;k ++)
{
g[i][j][k] = charArray[k];
if(g[i][j][k] == 'S') start = new PIIs(i,j,k);
if(g[i][j][k] == 'E') end = new PIIs(i,j,k);
}
}
}
int distance = bfs();
if(distance == -1) System.out.println("Trapped!");
else System.out.println("Escaped in " + distance + " minute(s).");
}
}
}
python题解
from collections import deque
#deque比list有更低的时间和空间复杂度
def bfs(z, x, y):
dist[z][x][y] = 0
queue = deque()
queue.append((z, x, y))
while len(queue):
z, x, y = queue.popleft()
for i in range(6):
xx, yy, zz = x + dx[i], y + dy[i], z + dz[i]
if 0 <= zz < l and 0 <= xx < r and 0 <= yy < c \
and q[zz][xx][yy] != '#' and dist[zz][xx][yy] == -1:
dist[zz][xx][yy] = dist[z][x][y] + 1
if q[zz][xx][yy] == 'E':
return dist[zz][xx][yy]
queue.append((zz, xx, yy))
return -1
dz = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
while True:
l, r, c = map(int, input().split())
if l == 0:
break
dist = [[[-1] * c for _ in range(r)] for _ in range(l)]
start_x, start_y, start_z = 0, 0, 0
q = []
for i in range(l):
q_tmp = []
for j in range(r):
ipt = input()
for index, item in enumerate(ipt):
if item == 'S':
start_z, start_x, start_y = i, j, index
q_tmp.append(list(ipt))
to_next = input()
q.append(q_tmp)
distance = bfs(start_z, start_x, start_y)
if distance == -1:
print("Trapped!")
else:
print("Escaped in %d minute(s)." % distance)
