Submission #1189065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189065		peteza	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	60 ms	5052 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pip = pair<int, pii>;

int n, m;
priority_queue<pip, vector<pip>, greater<pip>> pq;
string mp[505];
int dist[505][505];
bool vis[505][505];

int getdir[505], getnum[505];
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};

int main() {
    getnum['N'] = 0; getnum['E'] = 1; getnum['S'] = 2; getnum['W'] = 3;
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> mp[i];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            dist[i][j] = 999999;
        }
    }
    dist[0][0] = 0; pq.emplace(0, pii(0, 0));
    while(!pq.empty()) {
        auto e = pq.top(); pq.pop();
        auto pos = e.second;
        if(vis[pos.first][pos.second]) continue;
        vis[pos.first][pos.second] = 1;
        if(mp[pos.first][pos.second] == 'X') continue;
        int cd = getnum[mp[pos.first][pos.second]];
        for(int ch=0;ch<4;ch++) {
            int ni = pos.first + di[cd], nj = pos.second + dj[cd];
            if(ni >= 0 && nj >= 0 && ni < n && nj < m) {
                if(dist[ni][nj] > e.first + ch) {
                    dist[ni][nj] = e.first + ch;
                    pq.emplace(dist[ni][nj], pii(ni, nj));
                }
            }
            cd++; if(cd >= 4) cd = 0;
        }
    }
    //for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cout << dist[i][j] << ' '; cout << '\n';}
    if(!vis[n-1][m-1]) cout << -1;
    else cout << dist[n-1][m-1];
}

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