Submission #1259067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259067		billylolwkwk	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	103 ms	27280 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vec vector
#define dbg(x) cout<<#x<<" = "<<x<<endl
struct node{ll x,y,d;};
struct com {
	bool operator()(const node&a, const node&b){
		return a.d>b.d;
	}
};

const ll INF=LLONG_MAX;
ll n,m;
vec<vec<char>>g;
vec<vec<ll>>a;
bool chk(ll x,ll y){if(x<1||y<1||x>n||y>m)return false;else return true;}
priority_queue<node,vec<node>,com>pq;
signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;g=vec<vec<char>>(n+1,vec<char>(m+1));
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)cin>>g[i][j];
	a=vec<vec<ll>>(n+1,vec<ll>(m+1,INF));
	pq.push({1,1,0});
	while(!pq.empty()){
		auto t=pq.top();pq.pop();
		ll x=t.x,y=t.y,d=t.d;
		if(a[x][y]<=d)continue;
		else a[x][y]=d;
		if(g[x][y]=='X')continue;
		if(g[x][y]=='N'){
			if(chk(x-1,y))pq.push({x-1,y,d});
			if(chk(x,y+1))pq.push({x,y+1,d+1});
			if(chk(x+1,y))pq.push({x+1,y,d+2});
			if(chk(x,y-1))pq.push({x,y-1,d+3});
		}
		if(g[x][y]=='E'){
			if(chk(x-1,y))pq.push({x-1,y,d+3});
			if(chk(x,y+1))pq.push({x,y+1,d});
			if(chk(x+1,y))pq.push({x+1,y,d+1});
			if(chk(x,y-1))pq.push({x,y-1,d+2});
		}
		if(g[x][y]=='S'){
			if(chk(x-1,y))pq.push({x-1,y,d+2});
			if(chk(x,y+1))pq.push({x,y+1,d+3});
			if(chk(x+1,y))pq.push({x+1,y,d});
			if(chk(x,y-1))pq.push({x,y-1,d+1});
		}
		if(g[x][y]=='W'){
			if(chk(x-1,y))pq.push({x-1,y,d+1});
			if(chk(x,y+1))pq.push({x,y+1,d+2});
			if(chk(x+1,y))pq.push({x+1,y,d+3});
			if(chk(x,y-1))pq.push({x,y-1,d});
		}
	}
	if(a[n][m]==INF)cout<<-1;else cout<<a[n][m];return 0;
}

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