UVa 929 : Number Maze

Posted on | In |  
Symbols : 1.2k 字

給定一個 M x N 的矩陣 A ，求 A1,1 到 AM,N 的最短路徑長

測資
Input :

2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5

Output :

24
15


解法

這題要解的就是 Single Source To Other Destinations 的 Shortest Path
我們考慮一下 2 種比較常見的演算法 :

Dijkstra Algorithm Bellman-Ford Algorithm
策略 Greedy Dynamic Program
可有負邊 不可 可
時間複雜度 O( N2 ) O( N3 )

由於此題目中邊的權重為 0 ~ 9，沒有負邊
因此選擇使用 Dijkstra Algorithm 更經濟實惠一點

不過在實作演算時我們需要稍微改變一點細節
紀錄與 Source 的最短距離的一為陣列要改為使用二維陣列
此外，我們選擇使用 priority queue 來找出最小邊
除了可以加速演算法，對這題來說也比較好實作


程式碼解說

  1. dist[m + 2][n + 2] :
    紀錄各點到 source (本題是 <1,1> ) 的距離，此外為了讓 index 從 1 開始，在 row 和 column 前面各加了一列(行)空白
    此外，為了方便計算，在最後面也各加了一列(行)空白
  2. checked[m + 2][n + 2] :
    紀錄該點使否已經是最短路徑，前後同樣加了空白
    並將空白行視為已經是最短路徑，比較方便計算


完整程式碼

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

template<typename T>
using Matrix = vector<vector<T>>;

constexpr int MAX = 999;
constexpr int INF = 100000;

// 放在 priority queue 中的儲存資料
struct Record
{
	int row;
	int col;
	int dist;	// 當前 ( row, col ) 到 source 的最短路徑

	Record(int p = 0, int t = 0, int d = 0) :row{ p }, col{ t }, dist{ d } {}
};

// 由於 c++ 的 priority queue 是 max priority queue，所以要相反定義
inline bool operator<(const Record &lhs, const Record &rhs)
{
	return lhs.dist > rhs.dist;
}

class Solution
{
public:
	Solution()
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}

	int calculate(const Matrix<int> &m, const int ROW, const int COL)
	{
		Record min_rec;
		priority_queue<Record> que;

		int mr, mc;

		// 初始化資料
		initialize(ROW, COL);

		// 加入起始點
		que.push(Record{ 1,1,m[1][1] });

		while (!checked[ROW][COL])
		{
			// get the min edge from the available edges with priority queue
			min_rec = extract_min(que);

			mr = min_rec.row;
			mc = min_rec.col;

			// set the edge to be checked
			dist[mr][mc] = min_rec.dist;
			checked[mr][mc] = true;

			// update the neighbor nodes
			update_and_relax(m, que, mr, mc);
		}

		return dist[ROW][COL];
	}

private:
	Matrix<int> dist;
	Matrix<bool> checked;

private:

	void initialize(const int ROW, const int COL)
	{
		dist.clear();
		checked.clear();

		dist.resize(ROW + 2, vector<int>(COL + 2, INF));
		checked.resize(ROW + 2, vector<bool>(COL + 2, false));

		// 將空白行視為已經是最短路徑 ( 方便計算 )
		initial_checked();
	}

	void initial_checked(void)
	{
		int i;
		int re = checked.size() - 1;
		int ce = checked[0].size() - 1;

		for (i = 0; i <= ce; ++i)
			checked[0][i] = checked[re][i] = true;

		for (i = 0; i <= re; ++i)
			checked[i][0] = checked[i][ce] = true;
	}

	Record extract_min(priority_queue<Record> &que) const
	{
		Record rec;

		if (!que.empty())
		{
			rec = que.top();
			que.pop();
		}

		return rec;
	}

	void update_and_relax(const Matrix<int> &m, priority_queue<Record> &que, const int now_r, const int now_c)
	{
		// 四個方向 : 左、右、下、上
		static const vector<pair<int, int>> DIR = { {0,-1} ,{0,1},{1,0},{-1,0} };

		int d, new_r, new_c;

		for (auto &dir : DIR)
		{
			new_r = now_r + dir.first;
			new_c = now_c + dir.second;

			if (!checked[new_r][new_c])
			{
				d = dist[now_r][now_c] + m[new_r][new_c];

				if (d < dist[new_r][new_c])
				{
					dist[new_r][new_c] = d;
					que.push(Record{ new_r, new_c, d });
				}
			}

		}
	}
};

int main(void)
{
	int total_case;
	int row, col;
	int r, c, n, ans;
	Solution s;

	Matrix<int> m(MAX + 1, vector<int>(MAX + 1));

	cin >> total_case;

	while (total_case--)
	{
		m.clear();

		cin >> row >> col;
		cin.get();

		m.resize(row + 2, vector<int>(col + 2, INF));

		for (r = 1; r <= row; ++r)
		{
			for (c = 1; c <= col; ++c)
			{
				cin >> n;
				m[r][c] = n;
			}
		}

		ans = s.calculate(m, row, col);

		cout << ans << endl;
	}
	
	return 0;
}


複雜度分析

看一下主要的程式碼架構部分

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
int calculate(const Matrix<int> &m, const int ROW, const int COL)
	{
		Record min_rec;
		priority_queue<Record> que;

		int mr, mc;

		// 初始化資料
		initialize(ROW, COL);

		// 加入起始點
		que.push(Record{ 1,1,m[1][1] });

		while (!checked[ROW][COL])
		{
			// get the min edge from the available edges with priority queue
			min_rec = extract_min(que);

			mr = min_rec.row;
			mc = min_rec.col;

			// set the edge to be checked
			dist[mr][mc] = min_rec.dist;
			checked[mr][mc] = true;

			// update the neighbor nodes
			update_and_relax(m, que, mr, mc);
		}

		return dist[ROW][COL];
	}

維護 priority queue

  1. min_rec = extract_min(que);
    extract a element from priority queue : O(logE)
  2. update_and_relax(m, que, mr, mc);
    迴圈次數 2 次 : O(1)
    如果有 push element in priority queue : O(logE)

每個頂點都會有 4 條邊 ( 上、下、右、左 )
所以總邊數 = 4 x M x N - M - N –> O(MN) –> O( V )

因此，本題的 Edge 可是大約視作為 Vertex 的數目，所以對 priority queue 的操作也可看為 O( logV )
此外每個邊皆用於 relaxation 一次，priority queue 的操作最多共執行 E 次
所以維護 priority queue 的時間複雜度為 O(VlogV)

迴圈

迴圈最多走訪 V 次

總時間

時間複雜度 : 迴圈 + 維護 priority queue = O(V + VlogV)

0%