1 files changed, 107 insertions, 0 deletions
diff --git a/9a.c b/9a.c
new file mode 100644
index 0000000..ea80d5f
--- /dev/null
+++ b/9a.c
@@ -0,0 +1,107 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#define MAX_SIZE 256
+
+static char *ReadLine(char *p, size_t size, FILE *fp)
+{
+    if ((p=fgets(p, size, fp)))
+    {
+        size_t l = strlen(p);
+
+        while(l && p[l-1] == '\n')
+        {
+            p[--l] = 0;
+        }
+    }
+
+    return p;
+}
+
+static int Lowest(char map[MAX_SIZE][MAX_SIZE],
+                  int x, int y, int width, int height)
+{
+    char val;
+
+    val = map[y][x];
+
+    return (y == 0 || map[y-1][x] > val) &&
+           (y == height - 1 || map[y+1][x] > val) &&
+           (x ==0 || map[y][x-1] > val) &&
+           (x == width -1 || map[y][x+1] > val);
+}
+
+static int BasinSize(char map[MAX_SIZE][MAX_SIZE],
+                     char fill[MAX_SIZE][MAX_SIZE],
+                     int x, int y, int width, int height)
+{
+    if ((x < 0 || x == width || y < 0 || y == height) ||
+        (map[y][x] == 9 || fill[y][x]))
+    {
+        return 0;
+    }
+    else
+    {
+        fill[y][x] = 1;
+        return 1 + BasinSize(map, fill, x - 1, y, width, height) +
+                   BasinSize(map, fill, x + 1, y, width, height) +
+                   BasinSize(map, fill, x, y - 1, width, height) +
+                   BasinSize(map, fill, x, y + 1, width, height);
+    }
+}
+
+static int Compare(const void *a, const void *b)
+{
+    const int *pa = a;
+    const int *pb = b;
+
+    return *pa - *pb;
+}
+
+int main(void)
+{
+    char buff[0x8000];
+    char map[MAX_SIZE][MAX_SIZE]={0};
+    char fill[MAX_SIZE][MAX_SIZE]={0};
+    int max[3] = {0};
+    int map_height = 0;
+    int map_width = 0;
+    int x = 0;
+    int y = 0;
+    int f = 0;
+
+    while(ReadLine(buff, sizeof buff, stdin))
+    {
+        map_width = strlen(buff);
+
+        for(f = 0; f < strlen(buff); f++)
+        {
+            map[map_height][f] = buff[f] - '0';
+        }
+
+        map_height++;
+    }
+
+    for(y = 0; y < map_height; y++)
+    {
+        for(x = 0; x < map_width; x++)
+        {
+            if (Lowest(map, x, y, map_width, map_height))
+            {
+                int basin = BasinSize(map, fill, x, y, map_width, map_height);
+
+                if (basin > max[0])
+                {
+                    max[0] = basin;
+
+                    qsort(max, 3, sizeof(max[0]), Compare);
+                }
+            }
+        }
+    }
+
+    printf("product = %d\n", max[0] * max[1] * max[2]);
+
+    return 0;
+}