Submission #592172

#	Time	Username	Problem	Language	Result	Execution time	Memory
592172		Kipras	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	202 ms	27812 KiB

adventure

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxN = 510;

ll n, m, dist[maxN][maxN];
string s[maxN];

ll solve(){

    for(int i = 0; i < maxN; i++){
        for(int x = 0; x < maxN; x++){
            dist[i][x]=-1;
        }
    }

    dist[0][0] = -1;
    priority_queue<pair<int, pair<ll, ll>>, vector<pair<int, pair<ll, ll>>>, greater<pair<int, pair<ll, ll>>>> q;
    q.push({0, {0, 0}});

    while (!q.empty()) {
        pair<int, pair<ll, ll>> v = q.top();
        q.pop();
        ll w = v.first;
        ll i = v.second.first;
        ll x = v.second.second;
        if(i<0||x<0||i>=n||x>=m)continue;
        if (dist[i][x]==-1) {
            dist[i][x]=w;
            if(s[i][x]=='X')continue;
            if(s[i][x]=='N'){
                q.push({dist[i][x], {i-1, x}});
                q.push({dist[i][x]+1, {i, x+1}});
                q.push({dist[i][x]+2, {i+1, x}});
                q.push({dist[i][x]+3, {i, x-1}});
            }
            if(s[i][x]=='E'){
                q.push({dist[i][x]+3, {i-1, x}});
                q.push({dist[i][x], {i, x+1}});
                q.push({dist[i][x]+1, {i+1, x}});
                q.push({dist[i][x]+2, {i, x-1}});
            }
            if(s[i][x]=='S'){
                q.push({dist[i][x]+2, {i-1, x}});
                q.push({dist[i][x]+3, {i, x+1}});
                q.push({dist[i][x], {i+1, x}});
                q.push({dist[i][x]+1, {i, x-1}});
            }
            if(s[i][x]=='W'){
                q.push({dist[i][x]+1, {i-1, x}});
                q.push({dist[i][x]+2, {i, x+1}});
                q.push({dist[i][x]+3, {i+1, x}});
                q.push({dist[i][x], {i, x-1}});
            }
        }
    }
    /*for(int i = 0; i < 4; i++){
        for(int x = 0; x < 4; x++){
            cout<<dist[i][x]<<" ";
        }
        cout<<endl;
    }*/
    return dist[n-1][m-1];
}

int main()
{

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

    cout<<solve();

    return 0;
}

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