Submission #703265

#	Time	Username	Problem	Language	Result	Execution time	Memory
703265		rainboy	Awesome Arrowland Adventure (eJOI19_adventure)	C11	100 / 100	18 ms	3596 KiB

adventure

#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 (stderr)

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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50