# UVA 929 - Number Maze
### 題意:
給一個數字迷宮，每一格上都有對應的權重，你可以上下左右移動 (不能斜著走)。
找出從起點 -- ==迷宮的最左上角==，到終點 -- ==迷宮的最右下角==最小花費 (權重) 的路徑。
### Sample Input:
第一行代表總共有幾組測資。
接下來每組測資:
* 第一行代表 maze 有幾行 (row)。
* 第二行代表 maze 有幾列 (column)。
* 接下來的 row 行，每行有 col 個整數，代表每格的權重。

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

### Sample Output:
輸出每組測資裡面最小花費 (權重) 的路徑。

24
15

### 程式碼:

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;

int row, col;

int Dijkstra(vector<vector<int>>& maz, vector<vector<int>>& visited, priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>& pq) {
	int cost = 0, i = 0, j = 0;
	while (!pq.empty()) {
		tie(cost, i, j) = pq.top(); pq.pop();
		if (visited[i][j] == 1) continue;
		if (i == row - 1 && j == col - 1) return cost;
		visited[i][j] = 1;

		if (j + 1 < col && visited[i][j + 1] != 1) pq.emplace(cost + maz[i][j + 1], i, j + 1);
		if (i + 1 < row && visited[i + 1][j] != 1) pq.emplace(cost + maz[i + 1][j], i + 1, j);
		if (j - 1 >= 0 && visited[i][j - 1] != 1) pq.emplace(cost + maz[i][j - 1], i, j - 1);
		if (i - 1 >= 0 && visited[i - 1][j] != 1) pq.emplace(cost + maz[i - 1][j], i - 1, j);
	}
	return cost;
}

int main() {
	int c; cin >> c;
	while (c--) {
		cin >> row >> col;
		vector<vector<int>> maz(row, vector<int>(col));
		vector<vector<int>> visited(row, vector<int>(col));
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				cin >> maz[i][j];
				visited[i][j] = 0;
			}
		}
		priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
		pq.emplace(maz[0][0], 0, 0);
		
		cout << Dijkstra(maz, visited, pq) << endl;
	}
	return 0;
}