Submission #696177

#	Time	Username	Problem	Language	Result	Execution time	Memory
696177		rainboy	Dangerous Skating (JOI16_skating)	C11	100 / 100	1530 ms	11304 KiB

skating

#include <stdio.h>
#include <string.h>

#define N	1000
#define M	1000

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int main() {
	static char cc[N][M + 1];
	static int dd[N * M], qu1[N * M], qu2[N * M];
	int n, m, cnt1, cnt2, g, h1, h2, is, js, it, jt, i, j, i_, j_, ij, ij_, d;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	scanf("%d%d%d%d", &is, &js, &it, &jt), is--, js--, it--, jt--;
	memset(dd, 0x3f, n * m * sizeof *dd);
	cnt1 = cnt2 = 0, h1 = h2 = 0;
	ij = is * m + js;
	dd[ij] = 0, qu1[cnt1++] = ij;
	while (h1 < cnt1 || h2 < cnt2) {
		ij = h2 == cnt2 || h1 < cnt1 && dd[qu1[h1]] < dd[qu2[h2]] ? qu1[h1++] : qu2[h2++], i = ij / m, j = ij % m, d = dd[ij];
		if (i == it && j == jt) {
			printf("%d\n", d);
			return 0;
		}
		for (g = 0; g < 4; g++) {
			i_ = i + di[g], j_ = j + dj[g], ij_ = i_ * m + j_;
			if (cc[i_][j_] == '#')
				continue;
			if (dd[ij_] > d + 2)
				dd[ij_] = d + 2, qu2[cnt2++] = ij_;
			while (cc[i_][j_] != '#')
				i_ += di[g], j_ += dj[g];
			i_ -= di[g], j_ -= dj[g];
			ij_ = i_ * m + j_;
			if (dd[ij_] > d + 1)
				dd[ij_] = d + 1, qu1[cnt1++] = ij_;
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skating.c: In function 'main':
skating.c:24:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |   ij = h2 == cnt2 || h1 < cnt1 && dd[qu1[h1]] < dd[qu2[h2]] ? qu1[h1++] : qu2[h2++], i = ij / m, j = ij % m, d = dd[ij];
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
skating.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
skating.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
skating.c:18:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d%d%d", &is, &js, &it, &jt), is--, js--, it--, jt--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22