BOJ. Cheese (2636)

Problem

Approach

At the start of each hour, flood-fill the empty cells reachable from the padded outside border. Any cheese cell adjacent to this exterior air melts during that hour. Collect all such cells first, then remove them together; cheese exposed only after this removal must wait until the next hour.

Keep the total cheese count before each melting round. When a round removes the last cheese, that saved count is the number immediately before the final melting hour. An initially empty board needs no rounds, so the answer is 0 hours and 0 cheese.

C++17

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int rows, cols;
    cin >> rows >> cols;

    // The extra empty border guarantees a safe exterior-air starting cell.
    vector<vector<int>> cheese(rows + 2, vector<int>(cols + 2, 0));
    int remaining = 0;
    for (int r = 1; r <= rows; ++r) {
        for (int c = 1; c <= cols; ++c) {
            cin >> cheese[r][c];
            remaining += cheese[r][c];
        }
    }

    int hours = 0;
    int beforeLastMelt = 0;
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};

    while (remaining > 0) {
        beforeLastMelt = remaining;
        vector<vector<char>> visited(rows + 2, vector<char>(cols + 2, false));
        vector<vector<char>> melts(rows + 2, vector<char>(cols + 2, false));
        queue<pair<int, int>> air;
        vector<pair<int, int>> toMelt;

        air.push({0, 0});
        visited[0][0] = true;
        while (!air.empty()) {
            auto [r, c] = air.front();
            air.pop();

            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= rows + 2 || nc < 0 || nc >= cols + 2) {
                    continue;
                }
                if (cheese[nr][nc]) {
                    if (!melts[nr][nc]) {
                        melts[nr][nc] = true;
                        toMelt.push_back({nr, nc});
                    }
                } else if (!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    air.push({nr, nc});
                }
            }
        }

        // Apply this hour's melt only after the exterior-air search is complete.
        for (auto [r, c] : toMelt) {
            cheese[r][c] = 0;
        }
        remaining -= static_cast<int>(toMelt.size());
        ++hours;
    }

    cout << hours << '\n' << beforeLastMelt << '\n';
    return 0;
}

For H melting rounds on an R × C board, each round visits O(R·C) cells, so the running time is O(H·R·C). The board, visit/melt markers, and work queues use O(R·C) space.