Submission #407012

#	Time	Username	Problem	Language	Result	Execution time	Memory
407012		Ronin13	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	128 ms	20320 KiB

adventure

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define INF 1e9+1;
using namespace std;


vector<vector<pii> >g(250001);
int n,m;
int conv(int r,int c){
    return r*m+c;
}

char c[501][501];

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>c[i][j];
            if(c[i][j]=='S'){
                if(i+1<n){
                    g[conv(i,j)].epb(conv(i+1,j),0);
                }
                if(j+1<m){
                    g[conv(i,j)].epb(conv(i,j+1),3);
                }
                if(i-1>=0){
                    g[conv(i,j)].epb(conv(i-1,j),2);
                }
                if(j-1>=0){
                    g[conv(i,j)].epb(conv(i,j-1),1);
                }
            }
            if(c[i][j]=='E'){
                if(j+1<m){
                    g[conv(i,j)].epb(conv(i,j+1),0);
                }
                if(i-1>=0){
                    g[conv(i,j)].epb(conv(i-1,j),3);
                }
                if(j-1>=0){
                    g[conv(i,j)].epb(conv(i,j-1),2);
                }
                 if(i+1<n){
                    g[conv(i,j)].epb(conv(i+1,j),1);
                }
            }
            if(c[i][j]=='N'){
                if(i-1>=0){
                    g[conv(i,j)].epb(conv(i-1,j),0);
                }
                if(j-1>=0){
                    g[conv(i,j)].epb(conv(i,j-1),3);
                }
                 if(i+1<n){
                    g[conv(i,j)].epb(conv(i+1,j),2);
                }
                if(j+1<m){
                    g[conv(i,j)].epb(conv(i,j+1),1);
                }
            }
            if(c[i][j]=='W'){
                 if(j-1>=0){
                    g[conv(i,j)].epb(conv(i,j-1),0);
                }
                 if(i+1<n){
                    g[conv(i,j)].epb(conv(i+1,j),3);
                }
                if(j+1<m){
                    g[conv(i,j)].epb(conv(i,j+1),2);
                }
                if(i-1>=0){
                    g[conv(i,j)].epb(conv(i-1,j),1);
                }
            }
        }
    }
    int s=0,f=conv(n-1,m-1);
    vector<int>d(500001,1e9+1);
    d[s]=0;
    set<pii>q;
    q.insert({0,s});
    while(!q.empty()){
        int v=q.begin()->s;
        q.erase(q.begin());
        for(pii k:g[v]){
            int to=k.f,len=k.s;
            if(d[to]>d[v]+len){
                q.erase({d[to],to});
                d[to]=d[v]+len;
                q.insert({d[to],to});
            }
        }
    }
    if(d[f]==1e9+1)cout<<-1;
    else cout<<d[f];
}
int main(){
    int t;t=1;
    while(t--){
        solve();
    }
}

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