uppga.c (2909B)
1 #include "common.h" 2 3 #define NDIRS 4 4 #define NMOVES 3 5 #define MAX_NBRS 2048 6 7 typedef struct { 8 int64_t r; 9 int64_t c; 10 size_t d; 11 uint64_t acc; 12 } nbr_t; 13 14 const int64_t dirm[4][2][2] = {{{0, -1}, {0, +1}}, 15 {{+1, 0}, {-1, 0}}, 16 {{0, -1}, {0, +1}}, 17 {{+1, 0}, {-1, 0}}}; 18 19 static inline size_t dirr(const int64_t dir[2]) { 20 if (dir[0] == 0) { 21 if (dir[1] == -1) 22 return 3; 23 return 1; 24 } else { 25 if (dir[0] == -1) 26 return 0; 27 return 2; 28 } 29 } 30 31 static inline void nbrs_append(nbr_t *out, size_t *nout, int64_t r, int64_t c, 32 size_t d, uint64_t acc) { 33 assert(*nout < MAX_NBRS); 34 out[*nout] = (nbr_t){.r = r, .c = c, .d = d, .acc = acc}; 35 (*nout)++; 36 } 37 38 static inline void pnbrs(nbr_t *out, size_t *nout, int64_t r, int64_t c, 39 size_t d, int64_t nr, int64_t nc, uint64_t **cost, 40 size_t lb, size_t ub) { 41 *nout = 0; 42 size_t i; 43 for (i = 0; i < 2; i++) { 44 int64_t dd[2] = {dirm[d][i][0], dirm[d][i][1]}; 45 size_t acc = 0; 46 size_t ste = 0; 47 int64_t rr = r; 48 int64_t cc = c; 49 while (0 <= r && r < nr && 0 <= c && c < nc && ste <= ub) { 50 rr += dd[0]; 51 cc += dd[1]; 52 ste++; 53 if (0 <= rr && rr < nr && 0 <= cc && cc < nc) { 54 acc += cost[rr][cc]; 55 if (ste >= lb) 56 nbrs_append(out, nout, rr, cc, dirr(dd), acc); 57 } 58 } 59 } 60 } 61 62 static inline size_t tuple_to_node(int64_t r, int64_t c, size_t d, size_t nc) { 63 return ((size_t)r) * nc * NDIRS + ((size_t)c) * NDIRS + d; 64 } 65 66 int main(int argc, char **argv) { 67 char **lines; 68 size_t nr = readlines(&lines, "input"); 69 70 size_t nc = strlen(lines[0]) - 1; 71 72 uint64_t **costs = malloc(nr * sizeof(*costs)); 73 size_t i, j, k, l, nnbrs, nv, nw; 74 for (i = 0; i < nr; i++) 75 costs[i] = malloc(nc * sizeof(**costs)); 76 for (i = 0; i < nr; i++) { 77 for (j = 0; j < nc; j++) { 78 costs[i][j] = (uint64_t)(lines[i][j] - '0'); 79 } 80 } 81 82 nbr_t *nbrs = malloc(MAX_NBRS * sizeof(*nbrs)); 83 size_t nvertices = nr * nc * NDIRS + 2; 84 wdg_t g; 85 wdg_init(&g, nvertices); 86 87 for (i = 0; i < nr; i++) { 88 for (j = 0; j < nc; j++) { 89 for (k = 0; k < NDIRS; k++) { 90 pnbrs(nbrs, &nnbrs, i, j, k, nr, nc, costs, 0, 2); 91 nv = tuple_to_node(i, j, k, nc); 92 for (l = 0; l < nnbrs; l++) { 93 nw = tuple_to_node(nbrs[l].r, nbrs[l].c, nbrs[l].d, nc); 94 wdg_add_edge(&g, nv, nw, nbrs[l].acc); 95 } 96 } 97 } 98 } 99 free(nbrs); 100 101 size_t start = nvertices - 2; 102 size_t end = nvertices - 1; 103 104 for (i = 0; i < NDIRS; i++) 105 wdg_add_edge(&g, tuple_to_node(nr - 1, nc - 1, i, nc), end, 0); 106 wdg_add_edge(&g, start, tuple_to_node(0, 0, 0, nc), 0); 107 wdg_add_edge(&g, start, tuple_to_node(0, 0, 3, nc), 0); 108 109 uint64_t tot = wdg_dijkstra(&g, start, end); 110 printf("%llu\n", tot); 111 }