Submission #984283

#	Time	Username	Problem	Language	Result	Execution time	Memory
984283		Acanikolic	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	90 ms	34752 KiB

adventure

#include <bits/stdc++.h>

#define int long long

#define pb push_back

#define F first

#define S second

const int N = 500 + 10;

const int inf = 2e9;

const int mod = 998244353;

using namespace std;

int dist[N * N],n,m;
vector<pair<int,int>>g[N * N];
char a[N][N];
bool was[N * N];

map<pair<char,char>,int>cost;

int f(int i,int j) {
	return (i - 1) * m + j;
}

char get(int x) {
	int i = x / m + 1;
	int j = x % m;
	return a[i][j];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	for(int i = 1; i < N * N; i++) dist[i] = inf;
	cost[{'N','N'}] = 0;
	cost[{'N','E'}] = 1;
	cost[{'N','S'}] = 2;
	cost[{'N','W'}] = 3;
	cost[{'E','E'}] = 0;
	cost[{'E','S'}] = 1;
	cost[{'E','W'}] = 2;
	cost[{'E','N'}] = 3;
	cost[{'S','S'}] = 0;
	cost[{'S','W'}] = 1;
	cost[{'S','N'}] = 2;
	cost[{'S','E'}] = 3;
	cost[{'W','W'}] = 0;
	cost[{'W','N'}] = 1;
	cost[{'W','E'}] = 2;
	cost[{'W','S'}] = 3;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if(a[i][j] == 'X') continue;
			if(i >= 2) g[f(i,j)].pb({f(i - 1,j),cost[{a[i][j],'N'}]});
			if(j >= 2) g[f(i,j)].pb({f(i,j - 1),cost[{a[i][j],'W'}]});
			if(i + 1 <= n) g[f(i,j)].pb({f(i + 1,j),cost[{a[i][j],'S'}]});
			if(j + 1 <= m) g[f(i,j)].pb({f(i,j + 1),cost[{a[i][j],'E'}]});
		}
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	dist[f(1,1)] = 0;
	pq.push({0,f(1,1)});
	while(!pq.empty()) {
		int dst = pq.top().F;
		int u = pq.top().S;
		pq.pop();
		if(was[u] || get(u) == 'X') continue;
		was[u] = true;
		for(auto X : g[u]) {
			if(dist[X.F] > dist[u] + X.S) {
				dist[X.F] = dist[u] + X.S;
				pq.push({dist[X.F],X.F});
			}
		}
	}
	if(dist[f(n,m)] == inf) dist[f(n,m)] = -1;
	cout << dist[f(n,m)];
    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:72:7: warning: unused variable 'dst' [-Wunused-variable]
   72 |   int dst = pq.top().F;
      |       ^~~

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