제출 #1241308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241308		silence25	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	38 / 100	22 ms	328 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<pair<char,char>,int>moves;
map<char,int>ii;;
map<char,int>jj;
vector<char>v={'E','S','W','N'};
const int inf = 1e9;
char a[600][600];
int 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(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            dis[i][j]=inf;
        }
    }
    priority_queue<pair<int,pair<int,int>>>q;
    for(auto it:v){
            int fi = 1+ii[it];
            int fj = 1+jj[it];
            if(fi<1 || fi>n || fj<0 || fj>m){
                continue;
            }
            if(dis[fi][fj]>0+moves[{a[1][1],it}]){
                dis[fi][fj]=0+moves[{a[1][1],it}];
                q.push({dis[fi][fj],{fi,fj}});
            }
        }
    while(!q.empty()){
        int i = q.top().second.first;
        int j = q.top().second.second;
        int k = q.top().first;
        q.pop();
        if(dis[i][j]<k || a[i][j]=='X'){
            continue;
        }
        for(auto it:v){
            int fi = i+ii[it];
            int fj = j+jj[it];
            if(fi<1 || fi>n || fj<0 || 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: 0 / 12
• Subtask 4: 16 / 16
• Subtask 5: 0 / 50