14948 군대탈출하기

다익스트라 문제다.

문제 조건중 향하던 방향으로만 점프해서 한칸을 건너뛸 수 있다는 조건이 있는데 아주 중요하다. 

도움닫기가 필요한 상황이 있기 때문이다.

6 5

0 0 0 0 3

3 3 3 0 3

0 0 3 0 0

0 3 3 3 3

0 3 3 3 3

0 0 0 0 0

이렇게 생긴 맵에서

(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (2,3) (2,1)

이런식으로 점프하기 위해 다시 돌아와야 하는 경우가 있으므로 배열 잡을 때 방향도 고려해야 한다.

#include <stdio.h>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, m, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }, a[101][101], d[101][101][5][2];
priority_queue < pair<int, pair<int, pair<int, pair<int, int>>>>> q;
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) 
        scanf("%d", &a[i][j]);
    // mv c pw x y
    q.push({ -a[0][0],{1,{0,{0,0}}} });
 
    while (!q.empty()) {
        int mv = -q.top().first;
        int c = q.top().second.first;
        int pw = q.top().second.second.first;
        int x = q.top().second.second.second.first;
        int y = q.top().second.second.second.second;
        q.pop();
        
        if (d[x][y][pw][c] != -1) continue;
        if (x == n - 1 && y == m - 1) {
            printf("%d\n", mv);
            return 0;
        }
        d[x][y][pw][c] = mv;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && d[nx][ny][i+1][c] == -1) 
                q.push({ -max(mv,a[nx][ny]),{c,{i+1,{nx,ny}}} });
 
            if (!c || (i+1)^pw) continue;
            nx += dx[i]; ny += dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || d[nx][ny][i+1][0] != -1) continue;
            q.push({ -max(mv,a[nx][ny]),{0,{i+1,{nx,ny}}} });
        }
    }
 
    return 0;
}