#include #include #include #include #include #include using namespace std; int main(int argc, char* argv[]) { int height_map[100*100]; for(int i = 0; i < 100; i++) { string in; cin >> in; for(int j = 0; j < 100; j++) { height_map[j+i*100] = (int)in[j]-(int)'0'; } } vector basins(3, 0); for(int i = 0; i < 100*100; i++) { if (i-100 >= 0 && height_map[i-100] <= height_map[i]) { continue; } if (i+100 < 100*100 && height_map[i+100] <= height_map[i]) { continue; } if (i-1 >= 0 && height_map[i-1] <= height_map[i]) { continue; } if (i+1 < 100*100 && height_map[i+1] <= height_map[i]) { continue; } queue> to_explore; to_explore.push(pair(i-100,i)); to_explore.push(pair(i+100,i)); to_explore.push(pair(i-1,i)); to_explore.push(pair(i+1,i)); set basin; basin.insert(i); while(!to_explore.empty()) { pair cur = to_explore.front(); to_explore.pop(); if (cur.first < 0 || cur.first >= 100*100) { continue; } if (height_map[cur.first] != 9 && height_map[cur.first] > height_map[cur.second]) { pair::iterator,bool> res = basin.insert(cur.first); if (res.second) { to_explore.push(pair(cur.first-100,cur.first)); to_explore.push(pair(cur.first+100,cur.first)); to_explore.push(pair(cur.first-1,cur.first)); to_explore.push(pair(cur.first+1,cur.first)); } } } basins.push_back(basin.size()); sort(basins.begin(), basins.end()); basins.erase(basins.begin()); } cout << basins[0]*basins[1]*basins[2] << endl; return 0; }