#include #include #include #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; }