Solve day 9 part 2

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);
 }