Submission #1181518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181518		zadniprovska	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	38 ms	12196 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<long long, long long>
#define ppll pair< long long, pair<long long, long long> >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const ll DIM = 507;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;

ll dist[DIM][DIM], a[DIM][DIM], vis[DIM][DIM];
priority_queue<ppll, vector<ppll>, greater<ppll> > q;

const vector<ll> dx {-1, 0, 1, 0};
const vector<ll> dy {0, 1, 0, -1};

void solve() {

    ll n, m;
    cin >> n >> m;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            char ch;
            cin >> ch;

            if (ch == 'N') a[i][j] = 0;
            else if (ch == 'E') a[i][j] = 1;
            else if (ch == 'S') a[i][j] = 2;
            else if (ch == 'W') a[i][j] = 3;
            else a[i][j] = -1;

            dist[i][j] = INF;
        }
    }

    if (a[1][1] == -1) {
        cout << -1 << el;
        return;
    }

    dist[1][1] = 0;
    q.push({0, {1, 1}});
    while (!q.empty()) {

        ll x = q.top().ss.ff, y = q.top().ss.ss;
        q.pop();

        if (x == n && y == m) break;

        if (vis[x][y] || a[x][y] == -1) continue;
        vis[x][y] = 1;

        for (int t=0; t<4; t++) {

            ll nx = x + dx[(a[x][y]+t)%4], ny = y + dy[(a[x][y]+t)%4];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;

            if (dist[nx][ny] > dist[x][y] + t) {
                dist[nx][ny] = dist[x][y] + t;

                q.push({dist[nx][ny], {nx, ny}});
            }
        }

    }

    if (dist[n][m] == INF) cout << -1 << el;
    else cout << dist[n][m] << el;


}



signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("nocross.in", "r", stdin);
    //freopen("nocross.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

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