제출 #1280277

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

adventure

#include "bits/stdc++.h"
using namespace std;
#define mod 998244353
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define N 24
#define maxn 505

ll n,m;
map<char,ll> cost;
string s[maxn];
ll a[maxn][maxn];

void solve(){
	cin>>n>>m;
	for(ll i=0; i<n; i++) cin>>s[i];
	for(ll j=0; j<n; j++){
		for(ll i=0; i<m; i++){
			if(s[j][i]=='E') s[j][i]='R';
			else if(s[j][i]=='N') s[j][i]='U';
			else if(s[j][i]=='S') s[j][i]='D';
			else if(s[j][i]=='W') s[j][i]='L';
		}
	}
	for(ll i=0; i<n; i++) for(ll j=0; j<m; j++) a[i][j]=1e15;
	cost['R']=1;
	cost['U']=2;
	cost['L']=3;
	cost['D']=4;
	a[n-1][m-1]=0;
	priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > pq;
	pq.push({0,{n-1,m-1}});
	while(!pq.empty()){
		pair<ll,pair<ll,ll> > p=pq.top();
		// cout<<p.ff<<' ';
		pq.pop();
		ll x=p.ss.ff,y=p.ss.ss;
		if(x>0 and (a[x][y]+(cost[s[x-1][y]]-cost['D']+4)%4)<a[x-1][y] and s[x-1][y]!='X'){
			a[x-1][y]=a[x][y]+(cost[s[x-1][y]]-cost['D']+4)%4;
			pq.push({a[x-1][y],{x-1,y}});
		}
		if(y>0 and (a[x][y]+(cost[s[x][y-1]]-cost['R']+4)%4)<a[x][y-1] and s[x][y-1]!='X'){
			a[x][y-1]=a[x][y]+(cost[s[x][y-1]]-cost['R']+4)%4;
			pq.push({a[x][y-1],{x,y-1}});
		}
		if(x+1<n and (a[x][y]+(cost[s[x+1][y]]-cost['U']+4)%4)<a[x+1][y] and s[x+1][y]!='X'){
			a[x+1][y]=a[x][y]+(cost[s[x+1][y]]-cost['U']+4)%4;
			pq.push({a[x+1][y],{x+1,y}});
		}
		if(y+1<m and (a[x][y]+(cost[s[x][y+1]]-cost['L']+4)%4)<a[x][y+1] and s[x][y+1]!='X'){
			a[x][y+1]=a[x][y]+(cost[s[x][y+1]]-cost['L']+4)%4;
			pq.push({a[x][y+1],{x,y+1}});
		}
	}
	if(a[0][0]==1e15) cout<<-1;
	else cout<<a[0][0];
}
 
int main(){
	// freopen("in.txt","w",stdout);
	// freopen("out.txt","r",stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll t=1;
	// cin>>t;
	while(t--) solve();
}

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