diff options
Diffstat (limited to '12.c')
| -rw-r--r-- | 12.c | 176 |
1 files changed, 176 insertions, 0 deletions
@@ -0,0 +1,176 @@ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +struct pos { + int x; + int y; + struct pos * next; +}; + + +struct pos * +pos_create(int x, int y, struct pos * next) +{ + struct pos * p = malloc(sizeof(struct pos)); + if (!p) + return NULL; + p->x = x; + p->y = y; + p->next = next; + return p; +} + + +void +pos_free(struct pos * p) +{ + if (!p) + return; + pos_free(p->next); + free(p); +} + + +int +visited(unsigned char c) +{ + return c & 0x80; +} + + +int +height(unsigned char c) +{ + c &= 0x7F; + + switch (c) { + case 'S': return 'a'; + case 'E': return 'z'; + } + return c; +} + + +int +tryvisit(unsigned char * range, int cols, int rows, struct pos const * from, int dx, int dy) +{ + int x, y; + unsigned char src, dst; + + x = from->x + dx; + y = from->y + dy; + + // Check bounds. + if (x < 0 || x >= cols - 1 + || y < 0 || y >= rows) + return 0; + + // Check if already visited + dst = range[x + y * cols]; + if (visited(dst)) + return 0; + + // Check height + src = range[from->x + from->y * cols]; + if (height(dst) > height(src) + 1) + return 0; + + // OK. We can visit, so mark the new position as visited. + range[x + y * cols] |= 0x80; + + return 1; +} + + +int +main() +{ + unsigned char * range, * p; + size_t rangesize, rangelen, bytes; + int cols, rows; + struct pos * front; + int steps; + + // Read hill range + rangesize = BUFSIZ; + rangelen = 0; + range = malloc(rangesize); + while ((bytes = fread(range + rangelen, 1, rangesize - rangelen, stdin)) > 0) { + rangelen += bytes; + if (rangelen == rangesize) { + rangesize += BUFSIZ; + if ((p = realloc(range, rangesize)) == NULL) { + fprintf(stderr, "realloc(%zu) failed\n", rangesize); + free(range); + return -1; + } + range = p; + } + } + + // Get cols/rows in hill range + if ((p = memchr(range, '\n', rangelen)) == NULL) { + fprintf(stderr, "No lines found in input!\n"); + free(range); + return -1; + } + cols = p - range + 1; + if (rangelen % cols != 0) { + fprintf(stderr, "Input length %zu is not a multiple of line length %d\n", + rangelen, cols); + free(range); + return -1; + } + rows = rangelen / cols; + + // Find start, and mark it as visited + if ((p = memchr(range, 'S', rangelen)) == NULL) { + fprintf(stderr, "No start position!\n"); + free(range); + return -1; + } + front = pos_create((p - range) % cols, (p - range) / cols, NULL); + range[front->x + front->y * cols] |= 0x80; + + // Take steps, widening the search front each iteration. + for (steps = 0; 1; ++steps) { + struct pos * nextfront = NULL; + struct pos * loc; + + for (loc = front; loc != NULL; loc = loc->next) { + if ((range[loc->x + loc->y * cols] & 0x7F) == 'E') + // We found the end point! + break; + + if (tryvisit(range, cols, rows, loc, -1, 0)) + nextfront = pos_create(loc->x - 1, loc->y, nextfront); + if (tryvisit(range, cols, rows, loc, +1, 0)) + nextfront = pos_create(loc->x + 1, loc->y, nextfront); + if (tryvisit(range, cols, rows, loc, 0, -1)) + nextfront = pos_create(loc->x, loc->y - 1, nextfront); + if (tryvisit(range, cols, rows, loc, 0, +1)) + nextfront = pos_create(loc->x, loc->y + 1, nextfront); + } + if (loc) { + // Create a duplicate of the final location at the start + // of the current search front + front = pos_create(loc->x, loc->y, front); + pos_free(nextfront); + break; + } + + pos_free(front); + front = nextfront; + } + + printf("Found end at %d,%d in %d steps\n", front->x, front->y, steps); + + pos_free(front); + free(range); + + return 0; +} + |