Submission #949772

#	Time	Username	Problem	Language	Result	Execution time	Memory
949772		rainboy	미로 (KPI13_maze)	C11	1 / 1	32 ms	632 KiB

C

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

#define N	100
#define M	100000
#define W	64
#define K	163

typedef unsigned long long ull;

void shift(ull *bb, int s) {
	int h, q, r;
	ull b;

	if (s == 0)
		return;
	if (s > 0) {
		q = s / W, r = s % W;
		for (h = K - 1; h >= 0; h--) {
			b = 0;
			if (h >= q) {
				b |= bb[h - q] << r;
				if (h > q && r > 0)
					b |= bb[h - q - 1] >> W - r;
			}
			bb[h] = b;
		}
	} else {
		s = -s, q = s / W, r = s % W;
		for (h = 0; h < K; h++) {
			b = 0;
			if (h + q < K) {
				b |= bb[h + q] >> r;
				if (h + q + 1 < K && r > 0)
					b |= bb[h + q + 1] << W - r;
			}
			bb[h] = b;
		}
	}
}

void and(ull *aa, ull *bb) {
	int h;

	for (h = 0; h < K; h++)
		aa[h] &= bb[h];
}

int find(ull *bb) {
	int h, i;

	i = -1;
	for (h = 0; h < K; h++)
		if (bb[h]) {
			if (i != -1 || (bb[h] & bb[h] - 1) != 0)
				return -2;
			i = 0;
			while (1ULL << i < bb[h])
				i++;
			i += h * W;
		}
	return i;
}

int main() {
	static char cc[N][N + 1], dd[M + 1];
	static ull aa[K], bb[K];
	int n, m, h, h_, i, j, ij;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	scanf("%s", dd);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (cc[i][j] == '0') {
				ij = (i + 1) * (n + 2) + (j + 1);
				aa[ij / W] |= 1ULL << ij % W;
			}
	memcpy(bb, aa, K * sizeof *aa);
	for (h = 0; h <= m; h++) {
		if ((ij = find(bb)) != -2)
			break;
		if (h == m) {
			printf("-1\n");
			return 0;
		}
		if (dd[h] == 'L')
			shift(bb, -1);
		else if (dd[h] == 'R')
			shift(bb, 1);
		else if (dd[h] == 'U')
			shift(bb, -(n + 2));
		else
			shift(bb, n + 2);
		and(bb, aa);
	}
	if (ij == -1) {
		printf("-1\n");
		return 0;
	}
	i = ij / (n + 2) - 1, j = ij % (n + 2) - 1;
	for (h_ = h; h_ < m; h_++) {
		if (dd[h] == 'L')
			j--;
		else if (dd[h] == 'R')
			j++;
		else if (dd[h] == 'U')
			i--;
		else
			i++;
		if (i < 0 || i >= n || j < 0 || j >= n || cc[i][j] == '1') {
			printf("-1\n");
			return 0;
		}
	}
	printf("%d\n", h);
	return 0;
}

Compilation message (stderr)

C.c: In function 'shift':
C.c:24:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   24 |      b |= bb[h - q - 1] >> W - r;
      |                              ^
C.c:35:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |      b |= bb[h + q + 1] << W - r;
      |                              ^
C.c: In function 'find':
C.c:55:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   55 |    if (i != -1 || (bb[h] & bb[h] - 1) != 0)
      |                            ~~~~~~^~~
C.c: In function 'main':
C.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
C.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
C.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%s", dd);
      |  ^~~~~~~~~~~~~~~
C.c:68:25: warning: 'ij' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  int n, m, h, h_, i, j, ij;
      |                         ^~

• Subtask 1: 1 / 1