Submission #790259

#	Time	Username	Problem	Language	Result	Execution time	Memory
790259		Ludissey	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	91 ms	6640 KiB

adventure

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>

#define long long int;
using namespace std;

int newVal(int nb, int dir) {
	if (nb > dir) return dir + (4 - nb);
	return dir - nb;
}

int r, c;
vector<vector<int>> grid;
vector<vector<int>> dist;
vector<vector<int>> visited;

pair<int, pair<int, int>> moves[4] = { { 0, {0, -1} }, { 1,{1, 0} }, { 2, {0, 1} }, { 3,{-1, 0} } };

signed main() {
	cin >> r >> c;
	grid.resize(c, vector<int>(r));
	dist.resize(c, vector<int>(r));
	visited.resize(c, vector<int>(r));

	for (int y = 0; y < r; y++)
	{
		for (int x = 0; x < c; x++)
		{
			char c;
			cin >> c;
			if (c == 'X') grid[x][y] = -1;
			else if (c == 'N') grid[x][y] = 0;
			else if (c == 'E') grid[x][y] = 1;
			else if (c == 'S') grid[x][y] = 2;
			else if (c == 'W') grid[x][y] = 3;
			dist[x][y] = 1000000000;
		}
	} 

	priority_queue<pair<int, pair<int,int>>> q;
	dist[0][0] = 0;
	q.push({ 0,{0,0 } });
	while (!q.empty()) {
		int x = q.top().second.first, y= q.top().second.second; q.pop();
		if (visited[x][y]) continue;
		visited[x][y] = true;
		if (grid[x][y] == -1)continue;
		for (int s = 0; s < 4; s++)
		{
			int i = x + moves[s].second.first; 
			int j = y + moves[s].second.second;
			if (i >= c || j >= r || min(i,j)<0) continue;

			int w = newVal(grid[x][y], moves[s].first);
			if (abs(dist[x][y]) + w < abs(dist[i][j])) {
				dist[i][j] = abs(dist[x][y]) + w;
				q.push({ -dist[i][j],{i,j} });
			}
		}
	}
	if (!visited[c - 1][r-1]) cout << -1 << "\n";
	else cout << dist[c-1][r-1] << "\n";
	return 0;
}

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