제출 #1173314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173314		achi12344321	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	50 / 100	2095 ms	716 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(m);
    int i;
    int cnt, x, y;
    rep(i, 0, m) cin >> grid[i];
    vector<vi> rotcnt(m, vi(n, INT_MAX));
    priority_queue<pair<int, pii>> pq;
    pq.push({0, {0, 0}});
    int ux, uy;
    rotcnt[x][y] = 0;
    while (!pq.empty()) {
        cnt = pq.top().first;
        tie(x, y) = pq.top().second;
        pq.pop();
        // cout << x << " " << y << " " << cnt << "\n";
        if (grid[x][y] == 'X' || rotcnt[x][y] < cnt) continue;
        rep(i, 0, 4) {
            ux = x+r[i];
            uy = y+c[i];
            if (ux < 0 || uy < 0 || ux >= m || 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]);
            pq.push({rotcnt[ux][uy], {ux, uy}});
        }
    }

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

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

// <= in continue;
// dijkstra

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