Submission #465188

#	Time	Username	Problem	Language	Result	Execution time	Memory
465188		Elias	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	101 ms	30036 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<vector<pair<int, int>>> adj;
vector<bool> visited;

int dijkstra(int s, int e)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, s});

	while (pq.size())
	{
		auto [dist, x] = pq.top();
		pq.pop();
		if (visited[x])
			continue;
		visited[x] = true;

		if (x == e)
			return dist;
		for (auto [d, c] : adj[x])
		{
			if (visited[c])
				continue;
			pq.push({d + dist, c});
		}
	}

	return -1;
}

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

	int n, m;
	cin >> m >> n;

	adj = vector<vector<pair<int, int>>>(n * m);
	visited = vector<bool>(n * m, false);

	vector<pair<int, int>> dirs{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

	string row;

	for (int y = 0; y < m; y++)
	{
		cin >> row;
		for (int x = 0; x < n; x++)
		{
			int dir = row[x];
			if (dir == 'X')
				continue;
			if (dir == 'N')
				dir = 0;
			if (dir == 'E')
				dir = 3;
			if (dir == 'S')
				dir = 2;
			if (dir == 'W')
				dir = 1;

			for (auto [pX, pY] : dirs)
			{
				int dist = dir;
				dir = (dir + 1) % 4;

				int newX = x + pX;
				int newY = y + pY;
				if (newX < 0 || newX >= n || newY < 0 || newY >= m)
					continue;

				adj[x + y * n].push_back({dist, newX + newY * n});
			}
		}
	}

	//throw exception();

	cout << dijkstra(0, n * m - 1);
}

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