Submission #696181

#	Time	Username	Problem	Language	Result	Execution time	Memory
696181		rainboy	Dangerous Skating (JOI16_skating)	C11	100 / 100	109 ms	24716 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 nxt[4][N][M], 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--;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			nxt[0][i][j] = cc[i][j] == '#' ? (i + 1) * m + j : nxt[0][i - 1][j];
			nxt[2][i][j] = cc[i][j] == '#' ? i * m + (j + 1) : nxt[2][i][j - 1];
		}
	for (i = n - 1; i >= 0; i--)
		for (j = m - 1; j >= 0; j--) {
			nxt[1][i][j] = cc[i][j] == '#' ? (i - 1) * m + j : nxt[1][i + 1][j];
			nxt[3][i][j] = cc[i][j] == '#' ? i * m + (j - 1) : nxt[3][i][j + 1];
		}
	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];
			if (cc[i_][j_] == '#')
				continue;
			ij_ = nxt[g][i][j];
			if (dd[ij_] > d + 1)
				dd[ij_] = d + 1, qu1[cnt1++] = ij_;
			ij_ = i_ * m + j_;
			if (dd[ij_] > d + 2)
				dd[ij_] = d + 2, qu2[cnt2++] = ij_;
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skating.c: In function 'main':
skating.c:34:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |   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