d793 - 00929 - Number Maze
題目描述
題目給定一個 N x M 的數字迷宮，每個格子都有一個成本值。要求從左上角 (0, 0) 到右下角 (N-1, M-1) 的最小成本路徑。只能向上下左右移動。
解題思路
將迷宮視為一個圖，每個格子是一個節點。節點之間的邊權值是移動到相鄰格子的成本。使用 Dijkstra 演算法尋找從起點到終點的最短路徑。
- 將二維迷宮轉換為一維的節點表示，使用
getID(x, y)函數將座標 (x, y) 轉換為節點編號。 - 建立鄰接表
vp，其中vp[i]儲存從節點 i 出發的所有邊，每條邊包含目標節點和邊權值。 - 初始化距離
dis陣列，將所有節點的距離設定為無限大，起點的距離設定為 0。 - 使用一個優先佇列
q(set) 來儲存待處理的節點，優先佇列按照距離排序。 - 當優先佇列不為空且終點的距離仍然是無限大時，從優先佇列中取出距離最小的節點。
- 如果該節點尚未被訪問過，則標記為已訪問，並更新其所有鄰居的距離。
- 如果鄰居的距離可以通過當前節點縮短，則更新鄰居的距離，並將鄰居添加到優先佇列中。
- 最後，輸出終點的距離加上起點的成本。
複雜度分析
- 時間複雜度: O(N*M log(N*M))，其中 N 和 M 是迷宮的尺寸。Dijkstra 演算法的時間複雜度為 O(E log V)，其中 E 是邊的數量，V 是節點的數量。在這個問題中，V = N*M，E = 4*N*M。
- 空間複雜度: O(N*M)，用於儲存距離陣列、訪問陣列、鄰接表和優先佇列。
程式碼
#include <iostream>
#include <queue>
#include <set>
#define INF 10000000
using namespace std;
int n,m,dis[1000005],a[1005][1005],vis[1000005],w[4][2]={{-1,0},{1,0},{0,1},{0,-1}},t;
vector < pair <int,int> > vp[1000005];
int getID(int x,int y){
return x*m+y;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> m;
int ed=getID(n-1,m-1);
for(int i=0;i<=n*m;++i){
dis[i]=INF;
vis[i]=0;
vp[i].clear();
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >> a[i][j];
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
for(int k=0;k<4;++k){
int x=i+w[k][0],y=j+w[k][1];
if(x>=0&&x<n&&y>=0&&y<m){
vp[getID(i,j)].push_back(make_pair(a[x][y],getID(x,y)));
}
}
}
}
dis[0]=0;
set <pair <int,int> > q; // dis : goto
pair <int,int> t;
q.insert(make_pair(0,0));
while(q.empty()==0&&dis[ed]==INF){
t = *q.begin();
q.erase(t);
int x=t.first,y=t.second;
if(vis[y]==0){
vis[y]=1;
for(auto it:vp[y]){
if(dis[it.second]>dis[y]+it.first){
q.erase({dis[it.second], it.second});
dis[it.second]=dis[y]+it.first;
q.insert({dis[it.second],it.second});//insert the edge which is shortest to {0,0}
}
}
}
}
cout << dis[ed]+a[0][0] << "\n";
}
}