09b.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <stdbool.h>
   5 #include <limits.h>
   6 #include <uthash.h>
   7
   8 struct point { int x; int y; };
   9 struct entry { struct point key; UT_hash_handle hh; };
  10
  11 #define push(x, y) {\
  12         if ((x) >= 1 && (y) >= 1 && (x) <= maxx+1 && (y) <= maxy+1)\
  13                 stack[sp++] = (struct point){x, y};\
  14         }
  15
  16 int basin(int grid[102][102], int maxx, int maxy, int x, int y)
  17 {
  18         printf("calculate basin for: %d,%d -- ", x, y);
  19         struct point stack[1000];
  20         memset(stack, 0, sizeof stack);
  21         struct entry *visited = NULL;
  22
  23         int sp = 0;
  24         int size = 0;
  25         stack[sp++] = (struct point){.x=x, .y=y};
  26
  27         struct point p;
  28         struct entry *e;
  29         memset(&p, 0, sizeof p);
  30         while(--sp >= 0) {
  31                 p = stack[sp];
  32                 HASH_FIND(hh, visited, &p, sizeof(struct point), e);
  33                 if (e)
  34                         continue;
  35
  36                 e = calloc(1, sizeof(struct entry));
  37                 e->key = p;
  38                 HASH_ADD(hh, visited, key, sizeof(struct point), e);
  39
  40                 if (grid[p.y][p.x] == 9)
  41                         continue;
  42                 size++;
  43
  44                 push(p.x+1, p.y);
  45                 push(p.x-1, p.y);
  46                 push(p.x, p.y+1);
  47                 push(p.x, p.y-1);
  48         }
  49         printf(" %d\n", size);
  50         return size;
  51 }
  52
  53 void insert(int tl[3], int s)
  54 {
  55         if (s > tl[0] && s <= tl[1])
  56                 tl[0] = s;
  57         if (s > tl[1] && s <= tl[2]) {
  58                 tl[0] = tl[1];
  59                 tl[1] = s;
  60         }
  61         if (s > tl[2]) {
  62                 tl[0] = tl[1];
  63                 tl[1] = tl[2];
  64                 tl[2] = s;
  65         }
  66 }
  67
  68 int main()
  69 {
  70         int grid[102][102];
  71         for (int i = 0; i<102; i++)
  72                 for (int j = 0; j<102; j++)
  73                         grid[i][j] = 9;
  74         int x = 1, y = 1;
  75         int maxx = 1;
  76         int c = 0;
  77         while((c = getchar()) != EOF) {
  78                 if (c == '\n') {
  79                         y++;
  80                         x = 1;
  81                 } else {
  82                         maxx = x > maxx ? x : maxx;
  83                         grid[y][x++] = c-'0';
  84                 }
  85         }
  86
  87         int tl[3] = {0};
  88         for (int cy = 1; cy<y; cy++)
  89                 for (int cx = 1; cx<maxx+1; cx++)
  90                         if (grid[cy][cx] < grid[cy+1][cx] &&
  91                                         grid[cy][cx] < grid[cy-1][cx] &&
  92                                         grid[cy][cx] < grid[cy][cx+1] &&
  93                                         grid[cy][cx] < grid[cy][cx-1])
  94                                 insert(tl, basin(grid, maxx, y, cx, cy));
  95         printf("%d %d %d\n", tl[0], tl[1], tl[2]);
  96         printf("%d\n", tl[0]*tl[1]*tl[2]);
  97 }