Problem Solving►UVa

UVa 929 - Number Maze

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

從最左上角開始走，目的地是右下角，請問如何走才可以使路徑上數字的和為最小值，並輸出此值。

Solution

用 Dijkstra’s Algorithm 找出最短路徑。

需要用 Priority Queue 來加速否則會拿 TLE，要稍微注意一下自訂型態時 std::priority_queue 的操作，如果有 overload operator ，要使用 const member function (確保不會動到任何 member data，儘管你真的沒動到)。

Code

UVa 929UVa 929 - Number Maze
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
88
89
90
91
92
93
94
95
96
97

#include<cstdio>
#include<queue>
#define IN(x,y,n,m) ((x)&&(x)<=(n)&&(y)&&(y)<=(m))
#define N 1000
using namespace std;

int maze[N][N];
bool isVisit[N][N];
int d[N][N];

int dijkstra(int n, int m);
int main()
{
    int Case, i, j;
    scanf("%d", &Case);

    while (Case--)
    {
        int n, m;
        scanf("%d%d", &n, &m);

        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                scanf("%d", &maze[i][j]);

        printf("%d\n", dijkstra(n, m));
    }

    return 0;
}
int dijkstra(int n, int m)
{
    struct Node
    {
        int x, y, w;
        Node(){};
        Node(int a, int b, int c) :x(a), y(b), w(c){}
        bool operator<(const Node& a)const{ return w>a.w; }//數字大的順位較低
    };

    const int dir[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };//上下左右

    priority_queue<Node> PQ;

    int i, j;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
        {
        d[i][j] = 1e9;
        isVisit[i][j] = false;
        }

    d[1][1] = maze[1][1];
    PQ.push(Node(1, 1, d[1][1]));

    int all = n*m;
    for (i = 0; i < all; i++)
    {
        int next_x = -1, next_y = -1;

        while (!PQ.empty())
        {
            Node node = PQ.top();
            PQ.pop();
            //取出離起點最近且沒走過的點
            if (!isVisit[node.x][node.y])
            {
                next_x = node.x;
                next_y = node.y;
                break;
            }
        }

        //已經找完
        if (next_x == -1 || (next.x == n&&next.y == m))
            break;

        isVisit[next_x][next_y] = true;

        //更新起點透過 (next_x,next_y) 到其他點的距離
        for (j = 0; j < 4; j++)
        {
            int x = next_x + dir[j][0], y = next_y + dir[j][1];
            if (IN(x, y, n, m))
                if (d[next_x][next_y] + maze[x][y] < d[x][y])
                {
                d[x][y] = d[next_x][next_y] + maze[x][y];
                PQ.push(Node(x, y, d[x][y]));
                }
        }
    }

    return d[n][m];
}