uppga.c (1347B)
1 #include "common.h" 2 3 static inline uint64_t nsize(graph_t *g, size_t start, size_t nsteps) { 4 size_t i; 5 SIMPLEQ_HEAD(listead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 6 uint64_t count = 0; 7 entry_t *e = malloc(sizeof(*e)); 8 9 e->node = start; 10 e->dist = 0; 11 SIMPLEQ_INSERT_TAIL(&head, e, entries); 12 13 set_u64p_t added; 14 set_u64p_init(&added); 15 uint64_t pp[2] = {e->node, e->dist}; 16 le_t tt; 17 set_u64p_insert(&added, pp); 18 19 while (!SIMPLEQ_EMPTY(&head)) { 20 e = SIMPLEQ_FIRST(&head); 21 SIMPLEQ_REMOVE_HEAD(&head, entries); 22 23 if (e->dist < nsteps) { 24 for (i = 0; i < g->nbrs[e->node].nmemb; i++) { 25 pp[0] = g->nbrs[e->node].data[i]; 26 pp[1] = e->dist + 1; 27 if (set_u64p_lookup(&tt, &added, pp) == SIZE_MAX) { 28 set_u64p_insert(&added, pp); 29 entry_t *ne = malloc(sizeof(*e)); 30 ne->node = g->nbrs[e->node].data[i]; 31 ne->dist = e->dist + 1; 32 SIMPLEQ_INSERT_TAIL(&head, ne, entries); 33 } 34 } 35 } else if (e->dist == nsteps) { 36 count++; 37 } 38 39 free(e); 40 } 41 42 set_u64p_clear(&added); 43 44 return count; 45 } 46 47 int main(int argc, char **argv) { 48 char **lines; 49 size_t nlines = readlines(&lines, "input"); 50 51 graph_t g; 52 size_t start; 53 read_grid(&g, &start, lines, nlines); 54 55 uint64_t count = nsize(&g, start, 64); 56 printf("%llu\n", count); 57 }