[BAE/<JOON> 문제풀이] 14948. 군대탈출하기

https://www.acmicpc.net/problem/14948

14948번: 군대탈출하기

서론

매우 일반적인 최단거리 문제

---

풀이

문제에서 '타일을 건너뛰어 다음 타일로 갈 수 있다.' 라고 써놔서 말 그대로 1칸만 뛰어넘는다는 소린 줄 알았는데 체스 룩 처럼 거리 제한 없는 점프였다. 나처럼 읽는 사람 있을 것 같은데 이것만 좀 신경쓰면 특별할 것 없는 최단거리 문제다.

4방향 일반이동, 4방향 점프이동 총 8가지 이동을 구현하고 각 지점마다 점프를 해서 온 최댓값 과 점프를 사용하지 않고 밟은 최댓값을 저장하면 된다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
struct node {
	int x, y, u, cnt;
};
struct cmp {
	bool operator()(node a, node b) {
		return a.cnt > b.cnt;
	}
};
int mvx[4] = { 0, 1, 0, -1 };
int mvy[4] = { 1, 0, -1, 0 };
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m; vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	priority_queue<node, vector<node>, cmp> q;
	vector<vector<vector<int>>> ch(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 21e8)));	
	q.push({ 1, 1, 0, arr[1][1] });
	ch[1][1][0] = arr[1][1];
	while (!q.empty()) {
		auto cur = q.top(); q.pop();
		if (cur.x == n && cur.y == m) {
			cout << cur.cnt << "\n";
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int mx = cur.x + mvx[i];
			int my = cur.y + mvy[i];			
			if (mx > n || my > m || mx < 1 || my < 1 || ch[mx][my][cur.u] <= cur.cnt) continue;
			int cnt = cur.cnt > arr[mx][my] ? cur.cnt : arr[mx][my];
			ch[mx][my][cur.u] = cnt;
			q.push({ mx, my, cur.u, cnt });
		}
		if (cur.u == 0) {
			for (int i = 0; i < 4; i++) {
				int mx = cur.x + mvx[i] * 2;
				int my = cur.y + mvy[i] * 2;
				if (mx > n || my > m || mx < 1 || my < 1 || ch[mx][my][1] <= cur.cnt) continue;
				int cnt = cur.cnt > arr[mx][my] ? cur.cnt : arr[mx][my];
				ch[mx][my][1] = cnt;
				q.push({ mx, my, 1, cnt });
			}
		}
	}
	return 0;
}