Submission #762020

#	Time	Username	Problem	Language	Result	Execution time	Memory
762020		DJeniUp	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	91 ms	10684 KiB

adventure

#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;
 
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 1000000000000000007
#define eps 0.0000000001

ll n,m,d[507][507],res[507][507];

priority_queue<pair3l,vector<pair3l>, greater<pair3l> >q;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='N')d[i][j]=3;
            if(c=='E')d[i][j]=0;
            if(c=='S')d[i][j]=1;
            if(c=='W')d[i][j]=2;
            if(c=='X')d[i][j]=4;
            res[i][j]=INF;
            d[0][j]=4;
            d[n+1][j]=4;
        }
        d[i][0]=4;
        d[i][m+1]=4;
    }
    res[1][1]=0;
    q.push({0,{1,1}});
    while(q.size()>0){
        ll m1=q.top().fr;
        ll x=q.top().sc.fr;
        ll y=q.top().sc.sc;
        q.pop();
        if(res[x][y]==m1 && d[x][y]!=4){
            if(res[x+1][y]>(5-d[x][y])%4+m1){
                res[x+1][y]=(5-d[x][y])%4+m1;
                q.push({res[x+1][y],{x+1,y}});
            }
            if(res[x-1][y]>(7-d[x][y])%4+m1){
                res[x-1][y]=(7-d[x][y])%4+m1;
                q.push({res[x-1][y],{x-1,y}});
            }
            if(res[x][y+1]>(4-d[x][y])%4+m1){
                res[x][y+1]=(4-d[x][y])%4+m1;
                q.push({res[x][y+1],{x,y+1}});
            }
            if(res[x][y-1]>(6-d[x][y])%4+m1){
                res[x][y-1]=(6-d[x][y])%4+m1;
                q.push({res[x][y-1],{x,y-1}});
            }
        }
    }
    if(res[n][m]==INF)cout<<-1<<endl;
    else cout<<res[n][m]<<endl;
 
    return 0;
}

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