09b.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdbool.h>
   4 #include <stdint.h>
   5
   6 struct point { uint8_t x; uint8_t y; };
   7 bool visited[102][102] = {0};
   8 int grid[102][102];
   9
  10 int basin(int x, int y)
  11 {
  12         struct point stack[100];
  13
  14         int sp = 0;
  15         int size = 0;
  16         stack[sp++] = (struct point){.x=x, .y=y};
  17
  18         struct point p;
  19         memset(&p, 0, sizeof p);
  20         while(--sp >= 0) {
  21                 p = stack[sp];
  22                 if (visited[p.y][p.x])
  23                         continue;
  24                 visited[p.y][p.x] = true;
  25
  26                 if (grid[p.y][p.x] == 9)
  27                         continue;
  28                 size++;
  29
  30                 if (!visited[p.y][p.x+1])
  31                         stack[sp++] = (struct point){.x=p.x+1, .y=p.y};
  32                 if (!visited[p.y][p.x-1])
  33                         stack[sp++] = (struct point){.x=p.x-1, .y=p.y};
  34                 if (!visited[p.y+1][p.x])
  35                         stack[sp++] = (struct point){.x=p.x, .y=p.y+1};
  36                 if (!visited[p.y-1][p.x])
  37                         stack[sp++] = (struct point){.x=p.x, .y=p.y-1};
  38         }
  39         return size;
  40 }
  41
  42 int main()
  43 {
  44         for (int i = 0; i<102; i++)
  45                 for (int j = 0; j<102; j++)
  46                         grid[i][j] = 9;
  47         int x = 1, y = 1;
  48         int maxx = 1;
  49         int c = 0;
  50         while((c = getchar()) != EOF) {
  51                 if (c == '\n') {
  52                         y++;
  53                         x = 1;
  54                 } else {
  55                         maxx = x > maxx ? x : maxx;
  56                         grid[y][x++] = c-'0';
  57                 }
  58         }
  59
  60         int tl[3] = {0};
  61         for (int cy = 1; cy<y; cy++) {
  62                 for (int cx = 1; cx<maxx+1; cx++) {
  63                         if (!visited[cy][cx]) {
  64                                 int s = basin(cx, cy);
  65                                 if (s >= tl[0]) {
  66                                         tl[2] = tl[1];
  67                                         tl[1] = tl[0];
  68                                         tl[0] = s;
  69                                 } else if (s >= tl[1]) {
  70                                         tl[2] = tl[1];
  71                                         tl[1] = s;
  72                                 } else if (s > tl[2]) {
  73                                         tl[2] = s;
  74                                 }
  75                         }
  76                 }
  77         }
  78         printf("%d\n", tl[0]*tl[1]*tl[2]);
  79 }