제출 #1312708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312708		penguin133	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	72 ms	7396 KiB

adventure

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int dist[1005][1005], a[1005][1005];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int main() {
	int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char x; cin >> x;
            if (x == 'N') a[i][j] = 0;
            else if (x == 'E') a[i][j] = 1;
            else if (x == 'S') a[i][j] = 2;
            else if (x == 'W') a[i][j] = 3;
            else a[i][j] = 4;
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dist[i][j] = 1e9;
    dist[1][1] = 0;
    priority_queue <pair <int, pair <int, int> >, vector <pair <int, pair <int, int> > >, greater <> > pq;
    pq.push({0, {1, 1}});
    while (!pq.empty()) {
        int z = pq.top().first, x = pq.top().second.first, y = pq.top().second.second;
        pq.pop();
        if (dist[x][y] < z) continue;
        if (a[x][y] == 4) continue;
        for (int i = a[x][y]; i < a[x][y] + 4; i++) {
            int c = i - a[x][y], d = i % 4;
            int x1 = x + dx[d], y1 = y + dy[d];
            if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
            if (dist[x1][y1] > z + c) {
                dist[x1][y1] = z + c;
                pq.push({z + c, {x1, y1}});
            }
        }
    }
    cout << (dist[n][m] >= 1e9 ? -1 : dist[n][m]);
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50