Submission #1127991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127991		heey	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	130 ms	18120 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define int long long
int h[200005];
struct g{int x, y, t;};
bool cmp(g l, g r){
    return l.t < r.t;
}
int df(char cur, char dir){
    if(cur == dir) return 0;
    if(cur == 'N') return 1 + df('E', dir);
    if(cur == 'E') return 1 + df('S', dir);
    if(cur == 'S') return 1 + df('W', dir);
    if(cur == 'W') return 1 + df('N', dir);

    return 0; 
}

signed main(){
    //ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));

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

    vector<vector<int>> d(n, vector<int>(m, INT_MAX));
    vector<vector<bool>> u(n, vector<bool>(m, false));
    d[0][0] = 0;

    multiset<g, decltype(&cmp)> pick(cmp);

    pick.insert({0, 0, 0});
    while(!pick.empty()){
        //if(d[n-1][m-1] != INT_MAX) break;

        int x, y;
        g cur = *pick.begin();
        pick.erase(pick.find(cur));



        x = cur.x;
        y = cur.y;
        if(d[x][y] == INT_MAX) break;


        if(u[x][y]) continue;
        u[x][y] = true;
        if(a[x][y] == 'X') continue;

        if(x > 0) {
            int tm = d[x][y] + df(a[x][y], 'N');
            if(d[x-1][y] > tm){
                d[x-1][y] = tm;
                pick.insert({x-1, y, tm});
            }
        }
        if(x < n-1){
            int tm =  d[x][y] + df(a[x][y], 'S');
            if(d[x+1][y] > tm){
                d[x+1][y] = tm;
                pick.insert({ x+1, y, tm});
            }
        }
        if(y > 0) {
            int tm  = d[x][y] + df(a[x][y], 'W');
            if(d[x][y-1] > tm){
                d[x][y-1] = tm;
                pick.insert({ x, y-1, tm});
            }
        }
        if(y < m-1) {
            int tm =  d[x][y] + df(a[x][y], 'E');
            if(d[x][y+1] > tm){
                d[x][y+1] = tm;
                pick.insert({x, y+1, tm});
            }
        }

    }

    if(d[n-1][m-1] == INT_MAX) cout << "-1";
    else cout << d[n-1][m-1];

    return 0;
}

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