제출 #868183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868183		mariza	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	81 ms	19400 KiB

adventure

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define N 200001
#define INF 1000000001

#define MID ((l+r)/2)
#define RANGE (r-l+1)

int main() {
    ll n, m;
    cin>>n>>m;

    char c;
    ll u[n][m], r[n][m], d[n][m], l[n][m];
    for(ll i=0; i<n; i++){
        for(ll j=0; j<m; j++){
            cin>>c;
            if(c=='N'){
                u[i][j]=0;
                r[i][j]=1;
                d[i][j]=2;
                l[i][j]=3;
            }
            else if(c=='E'){
                u[i][j]=3;
                r[i][j]=0;
                d[i][j]=1;
                l[i][j]=2;
            }
            else if(c=='S'){
                u[i][j]=2;
                r[i][j]=3;
                d[i][j]=0;
                l[i][j]=1;
            }
            else if(c=='W'){
                u[i][j]=1;
                r[i][j]=2;
                d[i][j]=3;
                l[i][j]=0;
            }
            else{
                u[i][j]=INF;
                r[i][j]=INF;
                d[i][j]=INF;
                l[i][j]=INF;
            }
            if(i==0){
                u[i][j]=INF;
            }
            else if(i==n-1){
                d[i][j]=INF;
            }
            if(j==0){
                l[i][j]=INF;
            }
            else if(j==m-1){
                r[i][j]=INF;
            }
        }
    }

    priority_queue <pair<ll,pair<ll,ll>>> q; q.push({0,{0,0}});
    ll dist[n][m];
    for(ll i=0; i<n; i++){
        for(ll j=0; j<m; j++){
            dist[i][j]=INF;
        }
    }
    dist[0][0]=0;
    ll pr[n][m]={};

    while(!q.empty()){
        ll i=q.top().second.first;
        ll j=q.top().second.second;
        q.pop();

        if(pr[i][j]){
            continue;
        }
        pr[i][j]=true;

        if(i>0 && dist[i][j]+u[i][j]<dist[i-1][j]){
            dist[i-1][j]=dist[i][j]+u[i][j];
            q.push({-(dist[i][j]+u[i][j]),{i-1,j}});
        }
        if(i<n-1 && dist[i][j]+d[i][j]<dist[i+1][j]){
            dist[i+1][j]=dist[i][j]+d[i][j];
            q.push({-(dist[i][j]+d[i][j]),{i+1,j}});
        }
        if(j>0 && dist[i][j]+l[i][j]<dist[i][j-1]){
            dist[i][j-1]=dist[i][j]+l[i][j];
            q.push({-(dist[i][j]+l[i][j]),{i,j-1}});
        }
        if(j<m-1 && dist[i][j]+r[i][j]<dist[i][j+1]){
            dist[i][j+1]=dist[i][j]+r[i][j];
            q.push({-(dist[i][j]+r[i][j]),{i,j+1}});
        }
//        for(ll i1=0; i1<n; i1++){
//            for(ll j1=0; j1<m; j1++){
//                cout<<setw(3)<<((dist[i1][j1]<INF)?dist[i1][j1]:-1);
//            }
//            cout<<endl;
//        }
//        cout<<endl<<q.top().first<<" "<<q.top().second.first<<" "<<q.top().second.second<<endl;
    }


    cout<<((dist[n-1][m-1]<INF)?dist[n-1][m-1]:-1);

    return 0;
}

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