【範例】SSSP on Unweighted Graph (BFS)
【題目敘述】c124: 00532 – Dungeon Master
【題目敘述】https://vjudge.net/problem/POJ-2251 (UVA 532 – Dungeon Master)
【解題想法】BFS 求最短路徑
- 三維迷宮問題。可以行走前後左右及上下六個方向。求起點(S)到終點(E)的最短路徑。
- 一個L層的立體地牢，每一層都有 R * C 格。格子內如果是石塊(“#”)表示無法通行。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Pt{
int x, y, z;
int t;
};
int L, R, C;
int a[31][31][31]; //3D dungeon
int dx[6] = {0, 0, 0, 0, 1, -1};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {1, -1, 0, 0, 0, 0};
int visited[31][31][31];
Pt S, E; //start, end
int bfs(){
//BFS
memset(visited, 0, sizeof(visited));
queue <Pt> q;
q.push(S);
visited[S.x][S.y][S.z] = 1;
while (q.size()){
Pt now = q.front();
q.pop();
if (now.x == E.x && now.y == E.y && now.z == E.z){
return now.t;
}
for (int i=0; i<6; i++){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
int nz = now.z + dz[i];
if (nx >= 0 && nx < L && ny >= 0 && ny < R && nz >= 0 && nz < C && a[nx][ny][nz] != '#' && visited[nx][ny][nz] == 0){
q.push({nx, ny, nz, now.t + 1});
visited[nx][ny][nz] = 1;
}
}
}
return -1;
}
int main() {
string s;
while (cin >> L >> R >> C){
if (L == 0 && R == 0 && C == 0) break;
// build the 3D dungeon
for (int i=0; i<L; i++){
for (int j=0; j<R; j++){
cin >> s;
for (int k=0; k<C; k++){
a[i][j][k] = s[k];
if (s[k] == 'S'){
S = {i, j, k, 0};
}
if (s[k] == 'E'){
E = {i, j, k, 0};
}
}
}
}
int Time = bfs();
if (Time > -1) cout << "Escaped in " << Time << " minute(s).\n";
else cout << "Trapped!\n";
}
return 0;
}
Python code (credit: Amy Chou)
def bfs():
q = [S]
visited[S[0]][S[1]][S[2]] = 1
while q:
x, y, z, t = q.pop(0)
if x == E[0] and y == E[1] and z == E[2]:
return t
for i in range(6):
nx = x + dx[i]
ny = y + dy[i]
nz = z + dz[i]
if nx >= 0 and nx < L and ny >= 0 and ny < R and nz >= 0 and nz < C and a[nx][ny][nz] != '#' and visited[nx][ny][nz] == 0:
q.append((nx, ny, nz, t+1))
visited[nx][ny][nz] = 1
return -1
#=== main ===
a = [[[None for _ in range(31)] for _ in range(31)] for _ in range(31)]
visited = [[[0 for _ in range(31)] for _ in range(31)] for _ in range(31)]
dx = [0, 0, 0, 0, 1, -1]
dy = [0, 0, 1, -1, 0, 0]
dz = [1, -1, 0, 0, 0, 0]
while True:
L, R, C = map(int, input().split())
if L == 0 and R == 0 and C == 0:
break
for i in range(L):
for j in range(R):
a[i][j] = list(input())
for k in range(C):
visited[i][j][k] = 0
if a[i][j][k] == 'S':
S = (i, j, k, 0)
if a[i][j][k] == 'E':
E = (i, j, k)
_ = input() #在一層描述完後有一列空白區隔
Time = bfs()
if Time != -1:
print(f"Escaped in {Time} minute(s).")
else:
print("Trapped!")