oj.uz

Submission #975987

# Submission time Handle Problem Language Result Execution time Memory
975987 2024-05-06T04:22:47 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 51 ms 11972 KB 
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
#define endl '\n'
using namespace std;

int N,M,a[505][505];
int cost[505][505];
pair<int, int> dir[4];
map<char, int> ma;
char c;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> p;

void solve() {
	cin >> N >> M;
	ma['N'] = 0;
	ma['E'] = 1;
	ma['S'] = 2;
	ma['W'] = 3;
	ma['X'] = -1;
	dir[0] = {-1, 0};
	dir[1] = {0, 1};
	dir[2] = {1, 0};
	dir[3] = {0, -1};
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> c;
			a[i][j] = ma[c];
			cost[i][j] = 1e9;
		}
	}
	cost[1][1] = 0;
	p.push({0, {1, 1}});
	while (!p.empty()) {
		int cur = p.top().f;
		int icur = p.top().s.f;
		int jcur = p.top().s.s;
		// cout << cur << ' ' << icur << ' ' << jcur << endl;
		p.pop();
		if (icur == N && jcur == M) {
			cout << cur << endl;
			return;
		}
		if (a[icur][jcur] == -1) continue;
		if (cur > cost[icur][jcur]) continue;
		for (int cst = 0; cst < 4; cst++) {
			auto dr = dir[(a[icur][jcur] + cst) % 4];
			int inxt = icur + dr.f;
			int jnxt = jcur + dr.s;
			int cnxt = cur + cst;
			if (inxt >= 1 && inxt <= N && jnxt >= 1 && jnxt <= M && cost[inxt][jnxt] > cnxt) {
				cost[inxt][jnxt] = cnxt;
				p.push({cnxt, {inxt, jnxt}});
			}
		}
	}
	cout << -1 << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tttt = 1;
	// cin >> tttt;
	while (tttt--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2508 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2392 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2392 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2508 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 4 ms 2652 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 6 ms 2920 KB Output is correct
38 Correct 2 ms 3416 KB Output is correct
39 Correct 48 ms 4700 KB Output is correct
40 Correct 51 ms 4952 KB Output is correct
41 Correct 7 ms 4440 KB Output is correct
42 Correct 48 ms 4740 KB Output is correct
43 Correct 47 ms 11972 KB Output is correct
44 Correct 9 ms 4440 KB Output is correct