Submission #636960

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636960	2022-08-30T17:59:04 Z	CyberCow	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	74 ms	17976 KB

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;
}

Compilation message

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	324 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	328 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct

Subtask #4

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	336 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #5

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	324 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	328 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	328 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	336 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	324 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	5 ms	468 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	5 ms	724 KB	Output is correct
38	Correct	2 ms	852 KB	Output is correct
39	Correct	44 ms	2592 KB	Output is correct
40	Correct	45 ms	2588 KB	Output is correct
41	Correct	8 ms	2516 KB	Output is correct
42	Correct	47 ms	2592 KB	Output is correct
43	Correct	74 ms	17976 KB	Output is correct
44	Correct	7 ms	1516 KB	Output is correct