題目： UVa - 929 - Number Maze

題目說明

給一張地圖，每個格子中都有一些數字，求從起點走到終點且沿途的數字和為最小值。

Input： 第一行為一個整數 T，表示有 T 組測資，後面兩行分別為兩個整數 N、M，表示地圖為 N * M，後面 N 行，每行會有 M 個數字，表示地圖。

Output： 輸出從起點走到終點最小的數字和。

解題思路

這個解法需要有 Dijkstra 演算法的概念。

使用 Dijkstra 搭配 Priority_queue 求解即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <climits>
#include <queue>

using namespace std;

// reference: https://ppt.cc/fDEWex

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct Val
{
    int x;
    int y;
    int cost;

    bool operator>(const Val& r) const { return cost > r.cost; }
};

// data
int N, M;                     // matrix is N * M
int maze[1001][1001];
int value[1001][1001];        // 從起點走到每個點的最短路徑
int d[] = { 0, 1, 0, -1, 0 }; // 偏移量
bool visited[1001][1001];
priority_queue<Val, vector<Val>, greater<Val>> pq; // min heap

void init()
{
    // 一開始將距離都設為最大值
    for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) value[i][j] = INT_MAX;
    fill(visited[0], visited[0] + 1001 * 1001, false);
}

void dijkstra()
{
    pq.push({ 0, 0, value[0][0] = maze[0][0] });

    while (!pq.empty())
    {
        auto [x, y, val] = pq.top();
        visited[y][x] = true;
        pq.pop();

        for (int i = 0; i < 4; ++i)
        {
            int dx = x + d[i], dy = y + d[i + 1];

            // 如果超出範圍或是走過
            if (dx < 0 || dx >= M || dy < 0 || dy >= N || visited[dy][dx]) continue;

            int tmp = val + maze[dy][dx];
            if (value[dy][dx] > tmp) pq.push({ dx, dy, value[dy][dx] = tmp });
        }
    }

    cout << value[N - 1][M - 1] << '\n';
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        cin >> N >> M;

        // 建圖
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j)
        {
            int val;
            cin >> val;
            maze[i][j] = val;
        }
            
        init();

        dijkstra();
    }
}

參考資料

UVa/UVa 929 - Number Maze.cpp at master · ajahuang/UVa