Submission #999839

#	Time	Username	Problem	Language	Result	Execution time	Memory
999839		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	191 ms	81056 KiB

adventure

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 5e2 + 10;

vector<vector<int>> aj[sz * sz];
char ad[] = {'N', 'S', 'W', 'E'};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int dis[sz * sz];
bool vi[sz * sz];
char g[sz][sz];
int m, n;

bool leg(int i, int j) {
    return 0 < i && 0 < j && i <= m && j <= n;
}

void dij(int i) {
    priority_queue<vector<int>> pq;
    pq.push({0, i});

    while (!pq.empty()) {
        vector<int> f = pq.top();
        pq.pop();
        if (vi[f[1]]) continue;
        for (vector<int> u : aj[f[1]]) {
            if (vi[u[1]]) continue;
            pq.push({f[0] + u[0], u[1]});
            dis[u[1]] = max(dis[u[1]], f[0] + u[0]);
            // if (u[1] == 1506) {
            //     cout << dis[u[1]] << ' ' << f[1] << ' ' << f[0] << ' ' << u[0] << '\n';
            // }
        }
        vi[f[1]] = true;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    map <char, int> cd;
    cd['W'] = 1, cd['N'] = 2, cd['E'] = 3, cd['S'] = 4;

    cin >> m >> n;

    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> g[i][j];
        }
    }

    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) {
            if ('X' == g[i][j]) continue;
            for (int u = 0; u < 4; u ++) {
                int dxx = i + dx[u];
                int dyy = j + dy[u];
                if (leg(dxx, dyy)) {
                    // int ds = (cd[g[i][j]] + 4 - cd[ad[u]]) % 4;
                    int ds = 0;
                    if (cd[g[i][j]] <= cd[ad[u]]) {
                        ds = cd[ad[u]] - cd[g[i][j]];
                    } else {
                        // cout << cd[a[u]] << ' ' << cd[g[i][j]] ;
                        ds = 4 - cd[g[i][j]] + cd[ad[u]];
                    }
                    // cout << i * 501 + j << ' ' << dxx * 501 + dyy << ' ' << ds << ' ' << g[i][j] << ' ' << ad[u] << '\n';
                    aj[i * 501 + j].push_back({-ds, dxx * 501 + dyy});
                }
            }
        }
    }

    fill_n(dis, m * 501 + n + 10, INT_MIN);

    dij(502);

    int r = dis[m * 501 + n];

    if (r == INT_MIN) {
        cout << "-1\n";
        return 0;
    }

    cout << -r << '\n';
}

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