제출 #785614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785614		alex_2008	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	88 ms	20456 KiB

adventure

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
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;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	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;
		}
	}
	vector <vector<pair<int, int>>> G(n * m + 1);
	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;
				}
			}
			int cost = 0;
			while (cost != 4) {
				if (ch(i + dx[ind], j + dy[ind])) {
					G[vertex[i][j]].push_back({ vertex[i + dx[ind]][j + dy[ind]], cost });
				}
				cost++;
				ind = (ind + 1) % 4;
			}
		}
	}
	vector <int> dist(n * m + 1, INF);
	dist[1] = 0;
	set <pair<int, int>> ms;
	ms.insert({ 0, 1 });
	while (!ms.empty()) {
		int v = ms.begin()->second; ms.erase(ms.begin());
		for (auto it : G[v]) {
			if (dist[v] + it.second < dist[it.first]) {
				ms.erase({dist[it.first], it.first});
				dist[it.first] = dist[v] + it.second;
				ms.insert({ dist[it.first], it.first });
			}
		}
	}
	if (dist[n * m] == INF) {
		cout << -1 << "\n";
		return 0;
	}
	cout << dist[n * m] << "\n";
}

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