c124 - 00532 - Dungeon Master
題目描述
題目描述一個三維迷宮，要求從起點 'S' 找到出口 'E' 的最短路徑，並輸出所需的最少時間。迷宮中 '#' 代表障礙物，'.' 代表可通行區域。如果無法到達出口，則輸出 "Trapped!"。
解題思路
本題可以使用廣度優先搜尋 (BFS) 演算法來解決。將迷宮視為一個三維網格，從起點開始，將所有可到達的鄰居加入佇列，並記錄每個位置的步數。當到達出口時，輸出步數。如果佇列為空且未到達出口，則表示無法到達出口，輸出 "Trapped!"。為了避免重複訪問，使用一個三維布林陣列 dp 記錄已訪問的節點。
複雜度分析
- 時間複雜度: O(L * R * C)，其中 L、R、C 分別是迷宮的層數、列數和行數。因為最壞情況下需要遍歷整個迷宮。
- 空間複雜度: O(L * R * C)，主要用於儲存佇列和
dp陣列。
程式碼
#include <iostream>
#include <queue>
using namespace std;
struct p{
int x,y,z,stp;
};
int il,jl,kl;
bool dp[50][50][50];
int w[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};//x,y,z,stp
char mp[50][50][50];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> il >> jl >> kl){
if(il==0&&jl==0&&kl==0)break;
queue < p > q;
int ans=-1;
for(int i=0;i<=40;++i)
for(int j=0;j<=40;++j)
for(int k=0;k<=40;++k){
mp[i][j][k]='#';
dp[i][j][k]=0;
}
for(int i=1;i<=il;++i){
for(int j=1;j<=jl;++j){
for(int k=1;k<=kl;++k){
cin >> mp[i][j][k];
if(mp[i][j][k]=='S'){
p a;
a.x=i;
a.y=j;
a.z=k;
a.stp=0;
q.push(a);
}
}
}
}
while(q.empty()==0&&ans==-1){
p a=q.front();
q.pop();
if(mp[a.x][a.y][a.z]=='#'||dp[a.x][a.y][a.z])continue;
dp[a.x][a.y][a.z]=1;
if(mp[a.x][a.y][a.z]=='E'){
ans=a.stp;
break;
}
for(int i=0;i<6;++i){
p b;
b.x=a.x+w[i][0];
b.y=a.y+w[i][1];
b.z=a.z+w[i][2];
b.stp=a.stp+1;
q.push(b);
}
}
if(ans==-1){
cout << "Trapped!\n";
}
else{
cout << "Escaped in " << ans << " minute(s).\n";
}
}
}