제출 #636960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636960		CyberCow	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	74 ms	17976 KiB

adventure

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
using namespace std;
using ll = long long;
int a[505][505];
int d[505][505];
set<pair<int, pair<int, int>>> s;


void solve()
{
	int n, m, i, j;
	cin >> n >> m;
	char c;
	for ( i = 1; i <= n; i++)
	{
		for ( j = 1; j <= m; j++)
		{
			cin >> c;
			if (c == 'N')
				a[i][j] = 1;
			if (c == 'E')
				a[i][j] = 2;
			if (c == 'S')
				a[i][j] = 3;
			if (c == 'W')
				a[i][j] = 4;
		}
	}
	if (n == 1 && m == 1)
	{
		cout << 0;
		return;
	}
	if (a[1][1] == 0)
	{
		cout << -1;
		return;
	}
	int oo = 1000000000;
	for ( i = 1; i <= n; i++)
	{
		for ( j = 1; j <= m; j++)
		{
			d[i][j] = oo;
		}
	}
	d[1][1] = 0;
	s.insert({ 0, {1, 1} });
	while (!s.empty())
	{
		pair<int, pair<int, int>> gag = *s.begin();
		i = gag.second.first;
		j = gag.second.second;
		s.erase(s.begin());
		if (gag.first > d[gag.second.first][gag.second.second])
			continue;
		if (d[i - 1][j] > gag.first + (1 - a[i][j] + 4) % 4)
		{
			d[i - 1][j] = gag.first + (1 - a[i][j] + 4) % 4;
			if (a[i - 1][j])s.insert({ d[i - 1][j], {i - 1, j} });
		}
		if (d[i][j + 1] > gag.first + (2 - a[i][j] + 4) % 4)
		{
			d[i][j + 1] = gag.first + (2 - a[i][j] + 4) % 4;
			if (a[i][j + 1])s.insert({ d[i][j + 1], {i, j + 1} });
		}
		if (d[i + 1][j] > gag.first + (3 - a[i][j] + 4) % 4)
		{
			d[i + 1][j] = gag.first + (3 - a[i][j] + 4) % 4;
			if (a[i + 1][j])s.insert({ d[i + 1][j], {i + 1, j} });
		}
		if (d[i][j - 1] > gag.first + 4 - a[i][j])
		{
			d[i][j - 1] = gag.first + 4 - a[i][j];
			if (a[i][j - 1])s.insert({ d[i][j - 1], {i, j - 1} });
		}
	}
	if (d[n][m] == oo)
		cout << -1;
	else
		cout << d[n][m];
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	int tt = 1, i = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

adventure.cpp: In function 'int main()':
adventure.cpp:101:14: warning: unused variable 'i' [-Wunused-variable]
  101 |  int tt = 1, i = 1;
      |              ^

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