Submission #1247833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247833		ethkc256	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	71 ms	30396 KiB

adventure

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

char grid[505][505] = {};
int coords[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector <pair <int, int>> graph[600005];
int distances[600005] = {};

void dijkstra(int start) {
    priority_queue <pair <int, int>> pq;
    distances[start] = 0;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int dist = -x.first;
        int node = x.second;
        if (dist > distances[node])
            continue;
        for (pair <int, int> P : graph[node]) {
            if (dist + P.first < distances[P.second]) {
                distances[P.second] = dist + P.first;
                pq.push(make_pair(-distances[P.second], P.second));
            }
        }
    }
}

int main() {
	int N, M;
    string S = "NESW";
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++)
            cin >> grid[i][j];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            distances[i * 1000 + j] = 1e6;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int f = -1;
            for (int idx = 0; idx < 4; idx++) {
                if (S[idx] == grid[i][j])
                    f = idx;
            }
            if (f == -1)
                continue;
            for (int n = 0; n <= 3; n++) {
                auto C = coords[(f + n) % 4];
                int start = i * 1000 + j;
                int dest = (i + C[0]) * 1000 + (j + C[1]);
                if ((1 <= i + C[0] && i + C[0] <= N) && (1 <= j + C[1] && j + C[1] <= M)) {
                    graph[start].emplace_back(make_pair(n, dest));
                }
            }
        }
    }
    dijkstra(1001);
    cout << (distances[N * 1000 + M] > N*M*3? -1 : distances[N * 1000 + M]);
} 

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