alan23273850 的刷題筆記
d793: 00929 - Number Maze
出處：https://zerojudge.tw/ShowProblem?problemid=d793
提交：https://zerojudge.tw/Submissions?problemid=d793&account=allllllan123456
問題：給定一個 $N\in[1,999]$ 乘以 $M\in[1,999]$ 的迷宮，每一格都有一個介於 0 到 9 的整數，請問從最左上角走到最右下角所經過的方格數字總和的最小值為何？
解法：因為這題的邊成本沒有負數，我們可以使用 Dijkstra’s 演算法求解。如何從迷宮轉為有向圖？我們可以視最左上角的數字為從出發點走至該格的成本，之後每當我從 A 格走到 B 格，就把這個過程當成一個有向邊而且其權重便為 B 格的數字，這樣也是一張合法的有向圖。
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef pair<int, int> pii;
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 priority_queue<pii, vector<pii>, greater<pii>> pq;
8 char m[999][999]; int T, dist[999*999]; cin >> T;
9 while (T--) { int N, M; cin >> N >> M;
10 for (int i=0; i<N; i++)
11 for (int j=0; j<M; j++)
12 cin >> m[i][j], m[i][j] -= '0';
13 memset(dist, 0x7f, sizeof dist);
14 dist[0] = m[0][0];
15 pq.push(pii(dist[0], 0));
16 while (!pq.empty()) {
17 int u = pq.top().second; pq.pop();
18 int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
19 for (int i=0; i<4; i++) {
20 int x = u/M + dx[i], y = u%M + dy[i];
21 if (0<=x && x<N && 0<=y && y<M) {
22 int v = x * M + y;
23 if (dist[v] > dist[u] + m[x][y])
24 dist[v] = dist[u] + m[x][y],
25 pq.push(pii(dist[v], v));
26 }
27 }
28 }
29 cout << dist[N*M-1] << '\n';
30 }
31 return 0;
32}