Submission #1252403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252403		onur8ocak	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	79 ms	32184 KiB

adventure

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

const int INF = 1e18;
map<char, int> mp = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};

int fark(char a, char b) {
    if (a == 'X') return INF;
    int tut = mp[b] - mp[a];
    if (tut < 0) tut += 4;
    return tut;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int total = n * m;
    vector<vector<pair<int, int>>> edges(total);

    auto id = [&](int i, int j) { return i * m + j; };

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int u = id(i, j);
            if (j + 1 < m) {
                int v = id(i, j + 1);
                int w1 = fark(a[i][j], 'E');
                int w2 = fark(a[i][j + 1], 'W');
                if (w1 != INF) edges[u].emplace_back(v, w1);
                if (w2 != INF) edges[v].emplace_back(u, w2);
            }
            if (i + 1 < n) {
                int v = id(i + 1, j);
                int w1 = fark(a[i][j], 'S');
                int w2 = fark(a[i + 1][j], 'N');
                if (w1 != INF) edges[u].emplace_back(v, w1);
                if (w2 != INF) edges[v].emplace_back(u, w2);
            }
        }
    }

    vector<int> dist(total, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[0] = 0;
    pq.emplace(0, 0);

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : edges[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    int result = dist[total - 1];
    cout << (result == INF ? -1 : result) << '\n';
}

int32_t main() {
    solve();
    return 0;
}

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