oj.uz

Submission #703265

# Submission time Handle Problem Language Result Execution time Memory
703265 2023-02-26T19:32:34 Z rainboy Awesome Arrowland Adventure (eJOI19_adventure) C
100 / 100
 18 ms 3596 KB 
#include <stdio.h>

#define N	500
#define M	500

int di[] = { 0, -1, 0, 1 };
int dj[] = { -1, 0, 1, 0 };
char map[] = "WNES";

int main() {
	static char cc[N][M + 1];
	static int dd[N * M], qu[4][N * M], hh[4], cnt[4];
	int n, m, nm, f, f_, g, i, j, ij, ij_, d;

	scanf("%d%d", &n, &m), nm = n * m;
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (ij = 0; ij < nm; ij++)
		dd[ij] = nm * 5;
	dd[0 * m + 0] = 0, qu[0][cnt[0]++] = 0 * m + 0;
	while (1) {
		ij_ = -1, f_ = -1;
		for (f = 0; f < 4; f++)
			if (hh[f] < cnt[f]) {
				ij = qu[f][hh[f]];
				if (ij_ == -1 || dd[ij_] > dd[ij])
					ij_ = ij, f_ = f;
			}
		if (ij_ == -1) {
			printf("-1\n");
			return 0;
		}
		hh[f_]++;
		ij = ij_;
		i = ij / m, j = ij % m, d = dd[ij];
		if (i == n - 1 && j == m - 1) {
			printf("%d\n", d);
			return 0;
		}
		for (g = 0; g < 4; g++)
			if (map[g] == cc[i][j])
				break;
		if (g == 4)
			continue;
		for (f = 0; f < 4; f++) {
			int i_ = i + di[(g + f) % 4], j_ = j + dj[(g + f) % 4], ij_ = i_ * m + j_;

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && dd[ij_] > d + f)
				dd[ij_] = d + f, qu[f][cnt[f]++] = ij_;
		}
	}
	return 0;
}

Compilation message

adventure.c: In function 'main':
adventure.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d", &n, &m), nm = n * m;
      |  ^~~~~~~~~~~~~~~~~~~~~
adventure.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 292 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 288 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 300 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 296 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 2 ms 468 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 2 ms 560 KB Output is correct
38 Correct 1 ms 596 KB Output is correct
39 Correct 18 ms 2808 KB Output is correct
40 Correct 18 ms 2804 KB Output is correct
41 Correct 2 ms 1672 KB Output is correct
42 Correct 18 ms 2892 KB Output is correct
43 Correct 13 ms 3596 KB Output is correct
44 Correct 2 ms 1716 KB Output is correct