Submission #260126

#	Time	Username	Problem	Language	Result	Execution time	Memory
260126		tomsyd	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	165 ms	9060 KiB

adventure

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
vector<char> d = {'S','E','N','W'};
const int inf = LLONG_MAX/2;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	map<char,map<char,int>> dist;
	dist['N']['S'] = 2;
	dist['S']['N'] = 2;
	dist['E']['W'] = 2;
	dist['W']['E'] = 2;
	dist['W']['S'] = 3;
	dist['N']['W'] = 3;
	dist['E']['N'] = 3;
	dist['S']['E'] = 3;
	for (auto i:d){
		for (auto j:d){
			if (i == j) dist[i][j] = 0;
			else if (!dist[i].count(j)) dist[i][j] = 1;
		}
	}
	/*for (auto i:dist){
		for (auto j:i.second){
			cout << i.first << ' ' << j.first << ' ' << j.second << '\n';
		}
	}*/
	vector<string> v(n);
	for (int i=0; i<n; ++i) cin >> v[i];
	if (v[0][0] == 'X'){
		if (n == 1 and m == 1) cout << 0;
		else cout << -1;
		return 0;
	}
	vector<vector<int>> vu(n,vector<int>(m,inf));
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> q;
	q.emplace(0,0,0);
	vu[0][0] = 0;
	while (!q.empty()){
		auto f = q.top();
		int x,y,a;
		tie(a,x,y) = f;
		q.pop();
		for (int i=0; i<4; ++i){
			int nx = dir[i].first + x, ny = dir[i].second + y;
			a += dist[v[x][y]][d[i]];
			if (nx >= 0 and ny >= 0 and nx < n and ny < m and vu[nx][ny] > a){
				vu[nx][ny] = a;
				if (v[nx][ny] != 'X') q.emplace(a,nx,ny);
			}
			a -= dist[v[x][y]][d[i]];
		}
	}
	if (vu[n-1][m-1] == inf) cout << -1;
	else cout << vu[n-1][m-1];
	return 0;
}

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