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;
	}
}