Submission #1222803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222803		Aisha	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	126 ms	17024 KiB

adventure

#include "bits/stdc++.h"

using namespace std;

int inf = 1e9;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector <vector <int>> g(n + 1, vector <int> (m + 1));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            char c; int x = 0;
            cin >> c;  
            if (c == 'E') x = 0;
            if (c == 'S') x = 1;
            if (c == 'W') x = 2;
            if (c == 'N') x = 3;
            if (c == 'X') x = 4;
            g[i][j] = x;
        }
    }

    vector <vector <int>> dis(n + 1, vector <int> (m + 1, inf));
    vector <vector <int>> vis(n + 1, vector <int> (m + 1));

    priority_queue <vector <int>> pq; pq.push({0, 1, 1}); 

    auto dst = [](int x, int y, int z) -> int {
        if (z == 4) return 0;
        vector <int> v(4);
        if (x == 1) v = {1, 0, 3, 2};
        if (x == -1) v = {3, 2, 1, 0};
        if (y == 1) v = {0, 3, 2, 1};
        if (y == -1) v = {2, 1, 0, 3};
        return v[z];
    };

    auto push = [&](int x, int y, int a, int b) -> void {
        if (x <= 0 || y <= 0 || x > n || y > m || vis[x][y]) return;
        int dx = x - a, dy = y - b;
        int d = dst(dx, dy, g[a][b]) + dis[a][b];
        if (d > dis[x][y]) return;
        pq.push({-d, x, y});
        dis[x][y] = d;
    };
    
    while (!pq.empty()) {
        int x = pq.top()[1], y = pq.top()[2], d = -pq.top()[0];
        pq.pop();
        //cout << x << ' ' << y << ' ' << d << endl;

        if (vis[x][y]) continue;

        dis[x][y] = d;
        vis[x][y] = 1;
        if (g[x][y] == 4) continue;
        push(x + 1, y, x, y);
        push(x - 1, y, x, y);
        push(x, y + 1, x, y);
        push(x, y - 1, x, y);
    }

    if (vis[n][m]) cout << dis[n][m] << endl;
    else cout << -1 << endl;

    return 0;
}

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