/* Solution to Pouring Honey by Mees * * Basic flood fill. * * Expected answer: ACCEPTED. * */ #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); } } } sort(components.begin(), components.end()); reverse(components.begin(), components.end()); for(int j = 0; j <= (int)components.size(); j++) { if(H <= 0) { cout << j << endl; break; } H -= components[j]; } return 0; }