f671 - FJCU_109_Winter_Day1_Lab6 最短路徑
題目描述
題目要求計算從一個 N x M 的網格左上角 (1,1) 到右下角 (N,M) 的最短路徑長度。網格中包含可通行 ('.') 和障礙 ('#')，只能上下左右移動，且不能超出網格邊界。如果無法到達，則輸出 -1。
解題思路
本題可以使用深度優先搜尋 (DFS) 演算法來尋找最短路徑。DFS 從起點開始，不斷探索相鄰的合法節點（即未超出邊界且不是障礙物），並記錄當前路徑的長度。當到達終點時，比較當前路徑長度與已知的最短路徑長度，並更新最短路徑長度。
程式碼中，r[i][j] 陣列用於記錄從起點到網格中每個節點 (i, j) 的最短路徑長度。dfs 函數遞迴地探索網格，並更新 r[i][j] 的值。ans 變數用於儲存從起點到終點的最短路徑長度。
複雜度分析
- 時間複雜度: O(N*M)
- 空間複雜度: O(N*M)
程式碼
#include <iostream>
using namespace std;
int n,m,ans=-1,nm,r[11][11];
char a[11][11];
void dfs(int x,int y,int s){
if(x<0||y<0||x>=n||y>=m||a[x][y]=='#'||s>=nm||s>=r[x][y])return;
r[x][y]=s;
if(x==n-1&&y==m-1){
if(ans==-1){
ans=s;
}
else{
ans=min(ans,s);
}
return;
}
dfs(x+1,y,s+1);
dfs(x-1,y,s+1);
dfs(x,y+1,s+1);
dfs(x,y-1,s+1);
}
int main(){
cin >> n >> m;
nm=n*m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
r[i][j]=nm;
cin >> a[i][j];
}
}
dfs(0,0,0);
cout << ans;
}