Submission #1241316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241316		silence25	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	80 ms	9140 KiB

adventure

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
map<pair<char,char>,ll>moves;
map<char,ll>ii;;
map<char,ll>jj;
vector<char>v={'E','S','W','N'};
const ll inf = 1e18;
char a[600][600];
ll dis[600][600];
int main(){
    moves[{'E','E'}]=0;
    moves[{'E','S'}]=1;
    moves[{'E','W'}]=2;
    moves[{'E','N'}]=3;
    moves[{'S','S'}]=0;
    moves[{'S','W'}]=1;
    moves[{'S','N'}]=2;
    moves[{'S','E'}]=3;
    moves[{'W','W'}]=0;
    moves[{'W','N'}]=1;
    moves[{'W','E'}]=2;
    moves[{'W','S'}]=3;
    moves[{'N','N'}]=0;
    moves[{'N','E'}]=1;
    moves[{'N','S'}]=2;
    moves[{'N','W'}]=3;
    ii['S']=1;
    jj['S']=0;
    ii['N']=-1;
    jj['N']=0;
    ii['W']=0;
    jj['W']=-1;
    ii['E']=0;
    jj['E']=1;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
            dis[i][j]=inf;
        }
    }
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>>q;
    dis[1][1]=0;
    q.push({0,{1,1}});
    // for(auto it:v){
    //         ll fi = 1+ii[it];
    //         ll fj = 1+jj[it];
    //         if(fi<1 || fi>n || fj<1 || fj>m){
    //             continue;
    //         }
    //         if(dis[fi][fj]>moves[{a[1][1],it}]){
    //             dis[fi][fj]=moves[{a[1][1],it}];
    //             q.push({dis[fi][fj],{fi,fj}});
    //         }
    //     }
    while(!q.empty()){
        ll i = q.top().second.first;
        ll j = q.top().second.second;
        ll k = q.top().first;
        q.pop();
        if(dis[i][j]<k || a[i][j]=='X'){
            continue;
        }
        for(auto it:v){
            ll fi = i+ii[it];
            ll fj = j+jj[it];
            if(fi<1 || fi>n || fj<1 || fj>m){
                continue;
            }
            if(dis[fi][fj]>k+moves[{a[i][j],it}]){
                dis[fi][fj]=k+moves[{a[i][j],it}];
                q.push({dis[fi][fj],{fi,fj}});
            }
        }
    }
    if(dis[n][m]!=inf){
        cout<<dis[n][m];
    }else{
        cout<<-1;
    }
}

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