UVA929 Number Maze 题解

思路

简单看一下题目，可以理解为在网格上寻找从点 \((1,\,1)\) 到点 \((n,\,m)\) 的最短路，其中权值为点权。

我们可以考虑直接使用 Dijkstra 算法在网格上跑一遍最短路算法，求得答案。下面简述一下 Dijkstra 算法的过程：

1. 创建一个大小与顶点数量相等的数组 \(f\)，用于存储起始点到各个顶点的当前最短距离估计值。

2. 将起始点的距离值设置为起始点的点权，其他点的距离值设置为无穷大（或一个足够大的值）。

3. 将起始点加入优先队列，按照距离值从小到大进行排序。

4. 重复以下步骤直到优先队列为空：

   • 弹出队首元素，表示当前最短路径已确定。
   • 遍历队首元素的所有邻接网格，如果通过对首到达邻居的距离比当前记录的距离更短，则更新邻居的距离值。
   • 如果值更新了，那么将邻居其加入队列。

5. 最终得到的 \(f\) 数组即为起始点到各个点的最短距离。

这样就可以轻松的通过本题啦！

代码

#include <iostream>
#include <cstring>
#include <queue>

#define int long long
#define endl '\n'

using namespace std;

int t, n, m, a[1009][1009], f[1009][1009];
int xx[] = {-1, 1, 0, 0}, yy[] = {0, 0, -1, 1};

void dijkstra(int x, int y) {
    memset(f, 63, sizeof f);
    f[x][y] = a[x][y];
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({-f[x][y], {x, y}});
    while (!pq.empty()) {
        int fx = pq.top().second.first, fy = pq.top().second.second;
        pq.pop();
        for (int i = 0; i < 4; i++) {
            int nx = fx + xx[i], ny = fy + yy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m) {
                continue;
            }
            if (f[nx][ny] > f[fx][fy] + a[nx][ny]) {
                f[nx][ny] = f[fx][fy] + a[nx][ny];
                pq.push({-f[nx][ny], {nx, ny}});
            }
        }
    }
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        char ch;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> ch;
                a[i][j] = ch - '0';
            }
        }
        dijkstra(1, 1);
        cout << f[n][m] << endl;
    }
}