Submission #242112

#	Time	Username	Problem	Language	Result	Execution time	Memory
242112		valerikk	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	135 ms	23416 KiB

adventure

#include<bits/stdc++.h>
using namespace std;

const int N = 505, INF = 1e9 + 5;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
char a[N][N];
vector<pair<pair<int, int>, int>> g[N][N];
int dist[N][N];

inline bool check(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    map<char, int> mp;
    mp['N'] = 0;
    mp['E'] = 1;
    mp['S'] = 2;
    mp['W'] = 3;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> a[i][j];
            if(a[i][j] != 'X'){
                for(int k = 0; k < 4; k++){
                    int dst = k - mp[a[i][j]];
                    if(dst < 0){
                        dst += 4;
                    }
                    int x = i + dx[k], y = j + dy[k];
                    if(check(x, y)){
                        g[i][j].push_back({{x, y}, dst});
                    }
                }
            }
            dist[i][j] = INF;
        }
    }
    dist[0][0] = 0;
    set<pair<int, pair<int, int>>> st = {{0, {0, 0}}};
    while(!st.empty()){
        auto v = st.begin()->second;
        st.erase(st.begin());
        for(auto to : g[v.first][v.second]){
            int dst = dist[v.first][v.second] + to.second;
            if(dst < dist[to.first.first][to.first.second]){
                st.erase({dist[to.first.first][to.first.second], to.first});
                dist[to.first.first][to.first.second] = dst;
                st.insert({dist[to.first.first][to.first.second], to.first});
            }
        }
    }
    if(dist[n - 1][m - 1] == INF){
        cout << -1;
    } else{
        cout << dist[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