| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 949772 |
2024-03-19T16:51:34 Z |
rainboy |
미로 (KPI13_maze) |
C |
|
32 ms |
632 KB |
#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
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
428 KB |
Output is correct |
| 6 |
Correct |
1 ms |
428 KB |
Output is correct |
| 7 |
Correct |
32 ms |
628 KB |
Output is correct |
| 8 |
Correct |
28 ms |
604 KB |
Output is correct |
| 9 |
Correct |
28 ms |
632 KB |
Output is correct |
| 10 |
Correct |
28 ms |
604 KB |
Output is correct |
| 11 |
Correct |
28 ms |
604 KB |
Output is correct |
| 12 |
Correct |
27 ms |
612 KB |
Output is correct |
| 13 |
Correct |
27 ms |
600 KB |
Output is correct |
| 14 |
Correct |
30 ms |
604 KB |
Output is correct |
| 15 |
Correct |
28 ms |
600 KB |
Output is correct |
| 16 |
Correct |
1 ms |
600 KB |
Output is correct |
| 17 |
Correct |
1 ms |
604 KB |
Output is correct |
| 18 |
Correct |
1 ms |
440 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| 21 |
Correct |
1 ms |
604 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
604 KB |
Output is correct |
| 24 |
Correct |
1 ms |
540 KB |
Output is correct |
| 25 |
Correct |
1 ms |
604 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
348 KB |
Output is correct |
| 30 |
Correct |
0 ms |
348 KB |
Output is correct |
| 31 |
Correct |
1 ms |
348 KB |
Output is correct |
| 32 |
Correct |
0 ms |
348 KB |
Output is correct |
| 33 |
Correct |
1 ms |
436 KB |
Output is correct |
| 34 |
Correct |
1 ms |
348 KB |
Output is correct |
| 35 |
Correct |
1 ms |
348 KB |
Output is correct |
| 36 |
Correct |
0 ms |
348 KB |
Output is correct |
| 37 |
Correct |
0 ms |
348 KB |
Output is correct |
| 38 |
Correct |
0 ms |
348 KB |
Output is correct |
| 39 |
Correct |
1 ms |
348 KB |
Output is correct |
| 40 |
Correct |
0 ms |
348 KB |
Output is correct |
| 41 |
Correct |
0 ms |
348 KB |
Output is correct |
| 42 |
Correct |
1 ms |
348 KB |
Output is correct |
| 43 |
Correct |
0 ms |
348 KB |
Output is correct |
| 44 |
Correct |
0 ms |
348 KB |
Output is correct |
| 45 |
Correct |
1 ms |
348 KB |
Output is correct |
| 46 |
Correct |
1 ms |
348 KB |
Output is correct |
| 47 |
Correct |
0 ms |
348 KB |
Output is correct |
| 48 |
Correct |
0 ms |
348 KB |
Output is correct |
| 49 |
Correct |
1 ms |
344 KB |
Output is correct |
| 50 |
Correct |
1 ms |
344 KB |
Output is correct |
