d453 - 三、最短距離
題目描述
題目要求在一個由 0 和 1 組成的矩陣中，找到從起點到終點的最短路徑長度。0 代表可通行，1 代表障礙物。如果無法到達終點，則輸出 0。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。將矩陣視為一個圖，0 代表節點，相鄰的 0 之間有邊連接。DFS 從起點開始，向四周探索，並記錄到達每個節點的最小距離。在搜尋過程中，如果遇到障礙物 (1) 或已經訪問過的節點，則停止搜尋。最終，如果到達終點，則輸出記錄的最小距離；否則，輸出 0。
程式碼中，bmap 陣列儲存了地圖的資訊，amap 陣列儲存了從起點到每個節點的最小距離。dfs 函數遞迴地搜尋地圖，並更新 amap 陣列。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是矩陣的列數，m 是矩陣的行數。在最壞的情況下，DFS 需要訪問矩陣中的每個節點。
- 空間複雜度: O(nm)，主要來自於
bmap和amap陣列，以及 DFS 的遞迴堆疊空間。遞迴深度在最壞情況下可能達到 nm。
程式碼
#include <iostream>
using namespace std;
bool bmap[101][101];
int amap[101][101],n,xa,ya,x,y,xb,yb;
char t;
void dfs(int xx,int yy,int s){
if(xx>x||yy>y||xx<0||yy<0||bmap[xx][yy]||(amap[xx][yy]<=s&&amap[xx][yy]!=0))return;
if(amap[xx][yy]==0||amap[xx][yy]>s)
amap[xx][yy]=s;
dfs(xx+1,yy,s+1);
dfs(xx-1,yy,s+1);
dfs(xx,yy+1,s+1);
dfs(xx,yy-1,s+1);
}
int main(){
cin >> n;
while(n--){
cin >> x >> y >> xb >> yb >> xa >> ya;
for(int i=0;i<x;++i){
for(int j=0;j<y;++j){
amap[i][j]=0;
cin >> t;
bmap[i][j]=t-48;
}
}
dfs(xb-1,yb-1,1);
cout << amap[xa-1][ya-1] << "\n";
}
}