Submission #1211739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211739		mehralii	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	42 ms	1608 KiB

adventure

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define ins insert
#define F fist
#define S second

constexpr int MAXN = 1e5;
const int LOG = __lg(MAXN)+1;

constexpr int INF = 1e9;
constexpr int MOD = 1e9+7;
constexpr double EPS = 1e-8;

/*
	EJOI 2019, Day 2, problem A, 100p.
*/

int f(char f, char t){
	if (f == 'X'){
		return INF;
	}

	if (f == t){
		return 0;
	}

	if (f == 'W'){
		if (t == 'N'){
			return 1;
		} else if (t == 'E'){
			return 2;
		} else {
			return 3;
		}
	} else if (f == 'N'){
		if (t == 'W'){
			return 3;
		} else if (t == 'S'){
			return 2;
		} else {
			return 1;
		}
	} else if (f == 'E'){
		if(t == 'W'){
			return 2;
		} else if (t == 'S'){
			return 1;
		} else {
			return 3;
		}
	} else{
		if (t == 'W'){
			return 1;
		} else if (t == 'N'){
			return 2;
		} else {
			return 3;
		}
	}
}

int n, m;

bool ok(int tx, int ty){
	return 0 <= tx && tx < n && 0 <= ty && ty < m;
}

void solve(){
	cin >> n >> m;

	vector<string> g(n);
	for(auto& x: g){
		cin >> x;
	}

	vector<vector<int>> d(n, vector<int>(m, INF));
	set<tuple<int, int, int>> q;

	vector<int> dx = {1, -1, 0, 0};
	vector<int> dy = {0, 0, 1, -1};
	string v = "SNEW";

	q.ins({d[0][0] = 0, 0, 0});

	int dist, x, y;

	while(!q.empty()){
		tie(dist, x, y) = *q.begin();
		q.erase(q.begin());

		for(int k = 0; k < 4; k++){
			int tx = x + dx[k], ty = y + dy[k];
			if (ok(tx, ty)){
				if(tx != n-1 && ty != m-1 && g[tx][ty] == 'X'){
					continue;
				}
				if (dist + f(g[x][y], v[k]) < d[tx][ty]){
					q.erase({d[tx][ty], tx, ty});
					d[tx][ty] = dist + f(g[x][y], v[k]);
					q.ins({d[tx][ty], tx, ty});
				}
			}
		}
	}

	if (d[n-1][m-1] == INF){
		cout << "-1\n";
	} else{
		cout << d[n-1][m-1] << '\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++){
		solve();
	}
}

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