a982 - 迷宮問題#1
題目描述
題目給定一個 N x N 的迷宮，其中 '#' 代表障礙物，'.' 代表可通行路徑。起點固定在 (1, 1)，終點是 (n-1, n-1)。要求計算從起點到終點的最短路徑長度（包含起點和終點）。如果無法到達終點，則輸出 "No solution!"。
解題思路
本題可以使用深度優先搜尋 (DFS) 演算法來解決。DFS 從起點開始，不斷向四周探索，直到找到終點或所有可達路徑都已探索完畢。在探索過程中，我們需要記錄每個格子被訪問的時間，並確保只訪問時間較晚的格子，以避免無限迴圈。
程式碼中，m[x][y] 儲存了格子 (x, y) 被訪問的時間。如果 m[x][y] 為 -1，表示該格子是障礙物；如果 m[x][y] 為 0，表示該格子尚未被訪問。dfs 函數遞迴地探索迷宮，如果當前格子是可通行的且未被訪問或訪問時間晚於當前時間，則將其訪問時間設為當前時間，並遞迴地探索其相鄰的格子。
在 main 函數中，首先讀取迷宮的地圖，然後從起點 (1, 1) 開始呼叫 dfs 函數。最後，檢查終點 (n-2, n-2) 是否被訪問過。如果被訪問過，則輸出其訪問時間；否則，輸出 "No solution!"。
複雜度分析
- 時間複雜度: O(N^2)
- 空間複雜度: O(N^2)
程式碼
#include <iostream>
using namespace std;
int m[101][101],n;
void dfs(int x,int y,int t){
if(m[x][y]==0||m[x][y]>t){
m[x][y]=t;
if(x-1>=0&&m[x-1][y]!=-1){
dfs(x-1,y,t+1);
}
if(y-1>=0&&m[x][y-1]!=-1){
dfs(x,y-1,t+1);
}
if(x+1<n&&m[x+1][y]!=-1){
dfs(x+1,y,t+1);
}
if(y+1<n&&m[x][y+1]!=-1){
dfs(x,y+1,t+1);
}
}
return ;
}
int main(){
while(cin >> n){
char c;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin >> c;
if(c=='#')
m[i][j]=-1;
else
m[i][j]=0;
}
}
dfs(1,1,1);
if(m[n-2][n-2]==0)
cout << "No solution!\n";
else
cout << m[n-2][n-2] << "\n";
}
}