diff options
Diffstat (limited to '')
| -rw-r--r-- | 2021/day09.c | 30 |
1 files changed, 29 insertions, 1 deletions
diff --git a/2021/day09.c b/2021/day09.c index 44c20a1..dee6d5e 100644 --- a/2021/day09.c +++ b/2021/day09.c @@ -1,5 +1,6 @@ #include <stdio.h> #include <stdlib.h> +#include <string.h> static int h, w; static int grid[128][128]; static int adj(int *a, int y, int x) { @@ -10,6 +11,17 @@ static int adj(int *a, int y, int x) { if (x < w-1) a[n++] = grid[y][x+1]; return n; } +static int basin[128][128]; +static int flood(int y, int x) { + if (grid[y][x] == 9 || basin[y][x]) return 0; + int size = 1; + basin[y][x] = 1; + if (y > 0 && grid[y-1][x] > grid[y][x]) size += flood(y-1, x); + if (y < h-1 && grid[y+1][x] > grid[y][x]) size += flood(y+1, x); + if (x > 0 && grid[y][x-1] > grid[y][x]) size += flood(y, x-1); + if (x < w-1 && grid[y][x+1] > grid[y][x]) size += flood(y, x+1); + return size; +} int main(void) { size_t cap = 0; char *buf = NULL; @@ -20,6 +32,7 @@ int main(void) { h++; } int risk = 0; + int max1 = 0, max2 = 0, max3 = 0; for (int y = 0; y < h; ++y) for (int x = 0; x < w; ++x) { int a[4]; @@ -28,7 +41,22 @@ int main(void) { for (int i = 0; i < n; ++i) { if (a[i] <= grid[y][x]) m |= 1; } - if (!m) risk += 1 + grid[y][x]; + if (!m) { + risk += 1 + grid[y][x]; + memset(basin, 0, sizeof(basin)); + int size = flood(y, x); + if (size > max1) { + max3 = max2; + max2 = max1; + max1 = size; + } else if (size > max2) { + max3 = max2; + max2 = size; + } else if (size > max3) { + max3 = size; + } + } } printf("%d\n", risk); + printf("%d\n", max1 * max2 * max3); } |