1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#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) {
int n = 0;
if (y > 0) a[n++] = grid[y-1][x];
if (y < h-1) a[n++] = grid[y+1][x];
if (x > 0) a[n++] = grid[y][x-1];
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;
while (0 < getline(&buf, &cap, stdin)) {
for (w = 0; buf[w] && buf[w] != '\n'; ++w) {
grid[h][w] = buf[w] - '0';
}
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];
int n = adj(a, y, x);
int m = 0;
for (int i = 0; i < n; ++i) {
if (a[i] <= grid[y][x]) m |= 1;
}
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);
}
|