/* Solution to Pouring Honey by Mees * * Somewhat artificially takes very long at the end. * * Expected answer: TLE. * */ #include #include #include #include using namespace std; int main() { int H, m, n; cin >> H >> m >> n; vector> grid(m + 2, vector(m + n + 2, 1)); char c; for(int i = 1; i <= m; i++) { for(int j = 1 + i/2; j <= n + i/2; j++) { cin >> c; grid[i][j] = (c == '#'); } } vector> offsets = { make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1), make_pair(1, 1), make_pair(-1, -1) }; vector components; for(int i = 0; i < m + 2; i++) { for(int j = 0; j < m + n + 2; j++) { if(grid[i][j] == 0) { grid[i][j] = 1; int ct = 1; queue> q; q.push(make_pair(i, j)); while(!q.empty()) { auto p = q.front(); q.pop(); int curi = p.first; int curj = p.second; for(auto offset : offsets) { int nbi = curi + offset.first; int nbj = curj + offset.second; if(grid[nbi][nbj] == 0) { ct++; grid[nbi][nbj] = 1; q.push(make_pair(nbi, nbj)); } } } components.push_back(ct); } } } int comp_ct = 0; while(H > 0) { int largest = -1; int idx = -1; for(int i = 0; i < (int)components.size(); i++) { if(components[i] > largest) { largest = components[i]; idx = i; } } H -= largest; components[idx] = 0; comp_ct++; } cout << comp_ct << endl; return 0; }