# 題目: UVa 929 - Number Maze

# 題目說明

給你一張N * M的map，每格都會有值
求起點到終點(左上到右下)的最小數字和

---

INPUT:
第一行有一個整數T，代表有T筆測資
每筆測資第一行有兩個整數N、M，代表map的大小
接著會有N行，每行有M個整數，代表map的值

---

OUTPUT:
輸出從起點到終點(左上到右下)的最小數字和

# 解題方法

先建map，接著以dijkstra演算法搭配priority_queue建出起點到每一個點的最小路徑
最後輸出終點的值即可

# 參考程式碼

#include <iostream>
#include <memory.h>
#include <queue>
#include <tuple>

using namespace std;
typedef tuple<int, int, int> tp;

int N, M;
int map[1001][1001];
int vals[1001][1001];
bool vis[1001][1001];
int d[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
priority_queue< tp, vector<tp>, greater<tp> > pq;

void dijkstra()
{
	vals[0][0] = map[0][0];
	pq.push(make_tuple(map[0][0], 0, 0));

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

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + d[i][0];
			int ny = y + d[i][1];

			if (nx >= 0 && nx < N && ny >= 0 && ny < M && !vis[nx][ny])
			{
				int tmp = val + map[nx][ny];
				if (vals[nx][ny] == -1 || vals[nx][ny] > tmp)
				{
					vals[nx][ny] = tmp;
					pq.push(make_tuple(tmp, nx, ny));
				}
			}
		}
	}

	cout << vals[N - 1][M - 1] << "\n";
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;

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

		// init
		memset(map, 0, sizeof(map));
		memset(vis, false, sizeof(vis));
		memset(vals, -1, sizeof(vals));

		// store data in map
		for (int i = 0, val; i < N; ++i) for (int j = 0; j < M; ++j)
		{
			cin >> val;
			map[i][j] = val;
		}

		// dijkstra algorithm
		dijkstra();
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%20929/