e699 - 11624 - Fire!
題目描述
題目描述一個迷宮逃生問題。Joe位於迷宮中的某個位置，迷宮中存在火源。Joe和火每分鐘可以向上下左右移動一格。題目要求判斷Joe是否能在被火燒到之前逃離迷宮，如果可以，輸出逃離迷宮所需的最短時間。Joe可以從迷宮邊緣的任何位置逃離。
解題思路
本題可以使用雙向廣度優先搜尋 (BFS) 解決。首先，從火源出發進行 BFS，計算火到達每個位置所需的時間。然後，從 Joe 的起始位置出發進行 BFS，計算 Joe 到達迷宮邊緣所需的時間。在 Joe 的 BFS 中，需要考慮火的蔓延時間，即 Joe 到達某個位置的時間必須小於火到達該位置的時間。
具體步驟如下：
- 讀取迷宮地圖，記錄火源和 Joe 的起始位置。
- 使用 BFS 計算火到達每個位置所需的時間，並將結果儲存在
fire陣列中。 - 使用 BFS 計算 Joe 到達迷宮邊緣所需的時間，並將結果儲存在
road陣列中。在 BFS 過程中，如果 Joe 到達某個位置的時間大於或等於火到達該位置的時間，則停止搜尋。 - 如果 Joe 成功逃離迷宮，則輸出最短時間；否則，輸出 "IMPOSSIBLE"。
複雜度分析
- 時間複雜度: O(R * C)，其中 R 是迷宮的行數，C 是迷宮的列數。因為 BFS 最多會遍歷迷宮中的所有格子。
- 空間複雜度: O(R * C)，用於儲存
fire和road陣列，以及 BFS 的佇列。
程式碼
#include <iostream>
using namespace std;
char mp[1001][1001];
int fire[1001][1001],road[1001][1001];
int x,y,ans;
inline void bffs(int xx,int yy,int step){
if(fire[xx][yy]&&step>=fire[xx][yy])return;
fire[xx][yy]=step;
++step;
if(xx+1<x&&mp[xx+1][yy]!='#')
bffs(xx+1,yy,step);
if(xx-1>=0&&mp[xx-1][yy]!='#')
bffs(xx-1,yy,step);
if(yy+1<y&&mp[xx][yy+1]!='#')
bffs(xx,yy+1,step);
if(yy-1>=0&&mp[xx][yy-1]!='#')
bffs(xx,yy-1,step);
}
inline void bfs(int xx,int yy,int step){
if((ans&&step>=ans)||(fire[xx][yy]&&step>=fire[xx][yy])||(road[xx][yy]&&step>=road[xx][yy]))return;
road[xx][yy]=step;
if(xx==x-1||!xx||yy==y-1||!yy){
if(!ans)ans=step;
else ans=min(step,ans);
}
++step;
if(xx+1<x&&mp[xx+1][yy]!='#')
bfs(xx+1,yy,step);
if(xx-1>=0&&mp[xx-1][yy]!='#')
bfs(xx-1,yy,step);
if(yy+1<y&&mp[xx][yy+1]!='#')
bfs(xx,yy+1,step);
if(yy-1>=0&&mp[xx][yy-1]!='#')
bfs(xx,yy-1,step);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
cin >> x >> y;
ans=0;
for(int i(0);i<x;++i)
for(int j(0);j<y;++j){
fire[i][j]=0;
road[i][j]=0;
cin >> mp[i][j];
}
for(int i(0);i<x;++i)
for(int j(0);j<y;++j)
if(mp[i][j]=='F')
bffs(i,j,1);
for(int i(0);i<x;++i){
for(int j(0);j<y;++j){
if(mp[i][j]=='J'){
bfs(i,j,1);
i=x;
break;
}
}
}
if(ans)
cout << ans << "\n";
else
cout << "IMPOSSIBLE\n";
}
}