09b.c

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