Submission #1232823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232823		billylolwkwk	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	47 ms	8884 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vec vector
#define pll pair<ll,ll>
#define fr first
#define sc second
#define dbg(x) cout<<#x<<" = "<<x<<endl
struct dt{
	ll x,y,dist;
};
const vec<pll>off={{-1,0},{0,1},{1,0},{0,-1},{-1,0},{0,1},{1,0}};
const ll INF=LLONG_MAX;
ll n,m;
vec<vec<char>>g;
vec<vec<ll>>d;
bool chk(const ll x, const ll y){if(x<=0||x>n||y<=0||y>m)return false;return true;}
struct com{
	bool operator()(const dt&a, const dt&b){
		return a.dist>b.dist;
	}
};
priority_queue<dt,vec<dt>,com>pq; // Djikstra algorithm
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	g=vec<vec<char>>(n+1,vec<char>(m+1));
	d=vec<vec<ll>>(n+1,vec<ll>(m+1,INF));
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)cin>>g[i][j];
	pq.push({1,1,0});
	while(!pq.empty()){
		dt cur=pq.top();pq.pop();
		ll x=cur.x,y=cur.y,dist=cur.dist,offset; // Offset jika g[i][j]=='N'
		if(d[x][y]<=dist)continue;d[x][y]=dist;
		char dir=g[x][y];if(dir=='X')continue; // Ya gak usah dilanjutin
		if(dir=='N')offset=0;
		else if(dir=='E')offset=1;
		else if(dir=='S')offset=2;
		else if(dir='W')offset=3;
		for(ll i=offset;i<offset+4;i++){
			ll xx=x+off[i].fr;ll yy=y+off[i].sc; // Pergi kesebelahnya 
			if(!chk(xx,yy))continue; // Keluar dari map
			if(d[xx][yy]>dist+i-offset)pq.push({xx,yy,dist+i-offset});
		}
	}
	if(d[n][m]==INF)cout<<-1;else cout<<d[n][m];return 0;
}

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