제출 #441864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441864		nots0fast	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	110 ms	9048 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define mt make_tuple
#define MAX (int)(2*pow(10,6) + 5)
// #define cout out
// #define cin in
ll inf = pow(10, 18) + 100;
ll INF = pow(10, 9);
ll modulo = pow(10, 9) + 7;
double eps = 1e-10;

// start time 14 : 42

ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0,  1, 0,-1};
string dir = "NESW";

void deal(){
	ll n, m;
	cin>>n>>m;
	vector<vector<char> > arr(n, vector<char>(m));
	fori(n){
		forj(m){
			cin>>arr[i][j];
		}
	}
	vector<vector<ll> > dt(n, vector<ll>(m, inf));
	dt[0][0] = 0;
	priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll> >, greater<tuple<ll,ll,ll> > > pq;
	pq.push(mt(0,0,0));
	while(!pq.empty()){
		auto [val, x, y] = pq.top();
		pq.pop();
		if(dt[x][y]!=val){
			continue;
		}
		if(arr[x][y] == 'X'){
			continue;
		}
		ll wh = dir.find(arr[x][y]);
		fork(4){
			ll x1 = x+dx[k], y1 = y + dy[k];
			if(x1 > -1 && y1 > -1 && x1 < n && y1 < m){
				ll add = (k-wh+4)%4;
				if(dt[x][y] + add < dt[x1][y1]){
					dt[x1][y1] = dt[x][y] + add;
					pq.push(mt(dt[x1][y1], x1, y1));
				}
			}
		}
	}
	if(dt[n-1][m-1] == inf){
		dt[n-1][m-1] = -1;
	}
	cout<<dt[n-1][m-1];
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();  
}

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