uppga.c (1611B)
1 #include "common.h" 2 3 static inline void edge_adder(dg_t *g, char **lines, size_t nlines, 4 size_t ncols, size_t row, size_t col) { 5 char c = lines[row][col]; 6 // north 7 if (c != '<' && c != '>' && c != 'v' && row > 0 && 8 walkable(lines, row - 1, col)) { 9 dg_add_edge(g, idx(row, col, ncols), idx(row - 1, col, ncols)); 10 } 11 12 // east 13 if (c != '^' && c != '<' && c != 'v' && col < ncols - 1 && 14 walkable(lines, row, col + 1)) { 15 dg_add_edge(g, idx(row, col, ncols), idx(row, col + 1, ncols)); 16 } 17 18 // south 19 if (c != '^' && c != '<' && c != '>' && row < nlines - 1 && 20 walkable(lines, row + 1, col)) { 21 dg_add_edge(g, idx(row, col, ncols), idx(row + 1, col, ncols)); 22 } 23 24 // west 25 if (c != 'v' && c != '>' && c != '^' && col > 0 && 26 walkable(lines, row, col - 1)) { 27 dg_add_edge(g, idx(row, col, ncols), idx(row, col - 1, ncols)); 28 } 29 } 30 31 static inline void read_grid(dg_t *g, char **lines, size_t nlines) { 32 size_t i, j; 33 size_t ncols = strlen(lines[0]) - 1; 34 35 dg_init(g, nlines * ncols); 36 for (i = 0; i < nlines; i++) { 37 for (j = 0; j < ncols; j++) { 38 if (lines[i][j] == '.' || lines[i][j] == '>' || lines[i][j] == '<' || 39 lines[i][j] == 'v' || lines[i][j] == '^') 40 edge_adder(g, lines, nlines, ncols, i, j); 41 } 42 } 43 } 44 45 int main(int argc, char **argv) { 46 char **lines; 47 size_t nlines = readlines(&lines, "input"); 48 49 dg_t g; 50 read_grid(&g, lines, nlines); 51 52 size_t l = 0; 53 uint8_t visited[g.n]; 54 memset(visited, 0, g.n); 55 recursive_longest_path(visited, 1, g.n - 2, 0, &g, &l); 56 57 printf("%zu\n", l); 58 }