제출 #1256108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256108		rajinnyo	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	61 ms	4792 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
// JANGAN LUPA CEK PERLU LL NGGAK
#define pb push_back
#define pii pair<int,int>
#define fi first
#define inf INT_MAX
#define se second
#define ti tuple<int,int,int>
#define miku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int dis[501][501];
char a[501][501];
vector<char>arah={'N','E','S','W'};
vector<int>ax={-1,0,1,0};
vector<int>ay={0,1,0,-1};
signed main(){
    miku
    int n,m;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<ti,vector<ti>,greater<ti>>q;
    dis[1][1]=0;
    q.push({0,1,1});
    while(q.size()){
        auto [d,x,y]=q.top();
        q.pop();
        if(dis[x][y]<d || a[x][y]=='X')continue;
        int pos=0;
        for(int i=0;i<4;i++) if(arah[i]==a[x][y]) pos=i;
        for(int i=0;i<4;i++){
            int npos=(pos+i)%4;
            char c=arah[npos];
            int nx=x+ax[npos];
            int ny=y+ay[npos];
            bool yes=0;
            if(a[nx][ny]=='X' && (nx!=n|| ny!=m)) yes=1;
            // cout<<"TIDAK "<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<d<<' '<<i<<" "<<c<<" "<<arah[pos]<<endl;
            if(nx<1 || ny<1 || nx>n || ny>m || yes ||dis[nx][ny]<=d+i) continue;
            // cout<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<d<<' '<<i<<" "<<c<<" "<<arah[pos]<<endl;
            dis[nx][ny]=d+i;
            q.push({d+i,nx,ny});
        }
    }
    if(dis[n][m]==inf)cout<<-1;
    else cout<<dis[n][m];
}

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