제출 #577629

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

adventure

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define N 505


const int modulo = 1e9 + 7;
int arr[N][N], dist[N][N];

int main()
{
	//fileio();
	fastio();

	map<char, int> ind;
	ind['E'] = 0, ind['S'] = 1, ind['W'] = 2, ind['N'] = 3;
	pii dir[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	int n, m;
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char tmp;
			cin>>tmp;
			dist[i][j] = modulo;
			if (tmp == 'X') arr[i][j] = -1;
			else arr[i][j] = ind[tmp]; 
		}
	}

	dist[1][1] = 0;
	priority_queue<pair<int, pii>> q;
	q.push({0, {1, 1}});
	while(!q.empty())
	{
		int x = q.top().nd.st, y = q.top().nd.nd;
		int d = -q.top().st;
		q.pop();
		if (arr[x][y] == -1) continue;
		if (d > dist[x][y]) continue;
		for (int i = 0; i < 4; i++)
		{
			int a = dir[i].st, b = dir[i].nd;
			int di = dist[x][y] + (i - arr[x][y] + 4) % 4;
			if (dist[x + a][y + b] > di)
			{
				dist[x + a][y + b] = di;
				q.push({-di, {x + a, y + b}});
			}
		}
	}
	if (dist[n][m] >= modulo) cout<<-1<<endl;
	else cout<<dist[n][m]<<endl;
	cerr<<"time taken: "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0; 
}

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