Submission #785680

#	Time	Username	Problem	Language	Result	Execution time	Memory
785680		alex_2008	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	95 ms	61364 KiB

adventure

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
const int N = 550, INF = 1e9 + 10;
char a[N][N];
int vertex[N][N];
char dir[4] = { 'N', 'E', 'S', 'W' };
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n, m;
bool ch(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m) return true;
	return false;
}
vector <vector<pair<int, int>>> G;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	G.resize(4 * n * m + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			vertex[i][j] = (i - 1) * m + j;
		}
	}
	int sz = n * m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 'X') continue;
			int ind = 0;
			for (int k = 0; k < 4; k++) {
				if (a[i][j] == dir[k]) {
					ind = k;
					break;
				}
			}
			if (ch(i + dx[ind], j + dy[ind])) {
				G[vertex[i][j]].push_back({ vertex[i + dx[ind]][j + dy[ind]], 0 });
			}
			int cost = 1, prev = vertex[i][j];
			ind = (ind + 1) % 4;
			while (cost != 4) {
				G[prev].push_back({ ++sz, 1 }); prev = sz;
				if (ch(i + dx[ind], j + dy[ind])) {
					G[sz].push_back({ vertex[i + dx[ind]][j + dy[ind]], 0 });
				}
				cost++;
				ind = (ind + 1) % 4;
			}
		}
	}
	vector <int> d(4 * n * m + 1, INF);
	d[1] = 0;
	deque <int> q;
	q.push_back(1);
	while (!q.empty()) {
		int v = q.front(); q.pop_front();
		if (v == n * m) {
			cout << d[v] << "\n";
			return 0;
		}
		for (auto it : G[v]) {
			if (d[it.first] > d[v] + it.second) {
				d[it.first] = d[v] + it.second;
				if (it.second == 0) {
					q.push_front(it.first);
				}
				else {
					q.push_back(it.first);
				}
			}
		}
	}
	cout << -1 << "\n";
}

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