Submission #1173289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173289		achi12344321	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	0 / 100	1585 ms	167936 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define fastio cin.tie(0)->sync_with_stdio(0)
#define vi vector<int>

vector<char> di = {'N', 'E', 'S', 'W'};
vector<int> r = {-1, 0, 1, 0}, c = {0, 1, 0, -1};

int calTime(char a, char b) {
    int i = 0, ai = 0, bi = 0;
    rep(i, 0, 4) if (di[i] == a) {
        ai = i;
        break;
    }
    rep(i, 0, 4) if (di[i] == b) {
        bi = i;
        break;
    }
    if (ai <= bi) return bi-ai;
    return (bi-ai+4)%4;
}

int main () {
    fastio;
    int m, n;
    cin >> m >> n;
    vector<string> grid(n);
    int i;
    int cnt, x, y;
    rep(i, 0, n) cin >> grid[i];
    vector<vi> rotcnt(n, vi(n, INT_MAX));
    queue<pair<int, pii>> q;
    q.push({0, {0, 0}});
    int ux, uy;
    int base;
    rotcnt[x][y] = 0;
    while (!q.empty()) {
        cnt = q.front().first;
        tie(x, y) = q.front().second;
        q.pop();
        if (grid[x][y] == 'X') continue;
        rep(i, 0, 4) {
            if (di[i] == grid[x][y]) {base = i; continue;}
            ux = x+r[i];
            uy = y+c[i];
            if (ux < 0 || uy < 0 || ux >= n || uy >= n || rotcnt[ux][uy] < rotcnt[x][y]+calTime(grid[x][y], di[i])) continue;
            rotcnt[ux][uy] = rotcnt[x][y]+calTime(grid[x][y], di[i]);
            q.push({rotcnt[ux][uy], {ux, uy}});
        }
        ux = x+r[base];
        uy = y+c[base];
        if (!(ux < 0 || uy < 0 || ux >= n || uy >= n || rotcnt[ux][uy] < rotcnt[x][y])) {
            rotcnt[ux][uy] = rotcnt[x][y];
            q.push({rotcnt[ux][uy], {ux, uy}});
        }
    }

    rep(i, 0, n) {
        rep(j, 0,n) {
            cout << rotcnt[i][j] << " ";
        }
        cout << "\n";
    }

    cout << (rotcnt[n-1][n-1] == INT_MAX ? -1 : rotcnt[n-1][n-1]);
    return 0;
}

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