uppga.c (2710B)
1 #include "common.h" 2 3 void playa(char **lines, size_t nlines) { 4 board b = parse(lines, nlines); 5 b.lcm = 700; 6 7 set s; 8 s.n = 0; 9 s.nalloc = b.lcm * b.h * b.w; 10 s.d = calloc(s.nalloc, sizeof(*s.d)); 11 12 uint64_t *best = malloc(s.nalloc * sizeof(*best)); 13 memset(best, 0xff, s.nalloc * sizeof(*best)); 14 15 uint64_t i, r, x, y, nr, cb; 16 17 for (i = 0; i < b.lcm; i++) { 18 best[i * (b.w * b.h)] = i + 1; 19 s.d[i * (b.w * b.h)] = 1; 20 s.n++; 21 } 22 23 while (s.n != 0) { 24 i = 0; 25 while (s.d[i] == 0) 26 i++; 27 s.d[i] = 0; 28 s.n--; 29 30 x = i % (b.w); 31 y = (i / b.w) % b.h; 32 r = i / (b.w * b.h); 33 nr = (r + 1) % b.lcm; 34 cb = best[r * (b.w * b.h) + y * b.w + x]; 35 36 if (!intersects(&b, x, y, nr) && 37 best[nr * (b.w * b.h) + y * b.w + x] > cb + 1) { 38 best[nr * (b.w * b.h) + y * b.w + x] = cb + 1; 39 if (s.d[nr * (b.w * b.h) + y * b.w + x] == 0) { 40 s.d[nr * (b.w * b.h) + y * b.w + x] = 1; 41 s.n++; 42 } 43 } 44 45 if (x > 0 && !intersects(&b, x - 1, y, nr) && 46 best[nr * (b.w * b.h) + y * b.w + (x - 1)] > cb + 1) { 47 best[nr * (b.w * b.h) + y * b.w + (x - 1)] = cb + 1; 48 if (s.d[nr * (b.w * b.h) + y * b.w + (x - 1)] == 0) { 49 s.d[nr * (b.w * b.h) + y * b.w + (x - 1)] = 1; 50 s.n++; 51 } 52 } 53 54 if (x < b.w - 1 && !intersects(&b, x + 1, y, nr) && 55 best[nr * (b.w * b.h) + y * b.w + (x + 1)] > cb + 1) { 56 best[nr * (b.w * b.h) + y * b.w + (x + 1)] = cb + 1; 57 if (s.d[nr * (b.w * b.h) + y * b.w + (x + 1)] == 0) { 58 s.d[nr * (b.w * b.h) + y * b.w + (x + 1)] = 1; 59 s.n++; 60 } 61 } 62 63 if (y > 0 && !intersects(&b, x, y - 1, nr) && 64 best[nr * (b.w * b.h) + (y - 1) * b.w + x] > cb + 1) { 65 best[nr * (b.w * b.h) + (y - 1) * b.w + x] = cb + 1; 66 if (s.d[nr * (b.w * b.h) + (y - 1) * b.w + x] == 0) { 67 s.d[nr * (b.w * b.h) + (y - 1) * b.w + x] = 1; 68 s.n++; 69 } 70 } 71 72 if (y < b.h - 1 && !intersects(&b, x, y + 1, nr) && 73 best[nr * (b.w * b.h) + (y + 1) * b.w + x] > cb + 1) { 74 best[nr * (b.w * b.h) + (y + 1) * b.w + x] = cb + 1; 75 if (s.d[nr * (b.w * b.h) + (y + 1) * b.w + x] == 0) { 76 s.d[nr * (b.w * b.h) + (y + 1) * b.w + x] = 1; 77 s.n++; 78 } 79 } 80 } 81 82 uint64_t min = UINT64_MAX; 83 for (i = 0; i < b.lcm; i++) { 84 if (best[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)] < min) { 85 min = best[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)]; 86 } 87 } 88 89 printf("min = %llu\n", min); 90 } 91 92 int main(int argc, char **argv) { 93 char **lines; 94 size_t nlines = readlines(&lines, "input"); 95 printf("#lines: \t%lu\n", nlines); 96 97 printf("#cols : \t%lu\n", strlen(lines[0]) - 1); 98 99 playa(lines, nlines); 100 }