BOJ 17144 — Fine Dust Simulation

Problem: BOJ 17144 — Fine Dust Simulation · 한국어 · 日本語

Each second, every dusty cell spreads floor(dust / 5) to each in-bounds adjacent cell except an air-cleaner cell. All cells spread at the same time, so the amounts sent out must be accumulated in a separate grid before any dust values are changed. The cell keeps the portion that did not spread.

The two air cleaners occupy the first column in consecutive rows. The upper cleaner circulates air counterclockwise along the top boundary and the cells between it and the top edge; the lower cleaner circulates clockwise along the bottom boundary and the cells between it and the bottom edge. Shift dust one cell along each exact perimeter path, starting with zero dust leaving the cleaner. This also ensures that purifier cells remain -1 and dust entering the cleaner is removed.

Repeat diffusion and both circulation paths for T seconds, then sum only nonnegative cells. Each cycle visits the R * C grid for diffusion and O(R + C) perimeter cells for circulation, giving O(T * R * C) time and O(R * C) space.

C++17

#include <iostream>
#include <vector>

using namespace std;

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

    int rows, columns, seconds;
    cin >> rows >> columns >> seconds;

    vector<vector<int>> dust(rows, vector<int>(columns));
    int upper = -1;
    int lower = -1;
    for (int row = 0; row < rows; ++row) {
        for (int column = 0; column < columns; ++column) {
            cin >> dust[row][column];
            if (dust[row][column] == -1) {
                if (upper == -1) upper = row;
                else lower = row;
            }
        }
    }

    vector<vector<int>> change(rows, vector<int>(columns));
    constexpr int rowStep[] = {-1, 1, 0, 0};
    constexpr int columnStep[] = {0, 0, -1, 1};

    for (int second = 0; second < seconds; ++second) {
        for (int row = 0; row < rows; ++row) {
            for (int column = 0; column < columns; ++column) {
                change[row][column] = 0;
            }
        }

        for (int row = 0; row < rows; ++row) {
            for (int column = 0; column < columns; ++column) {
                if (dust[row][column] <= 0) continue;
                const int spread = dust[row][column] / 5;
                if (spread == 0) continue;

                int neighbors = 0;
                for (int direction = 0; direction < 4; ++direction) {
                    const int nextRow = row + rowStep[direction];
                    const int nextColumn = column + columnStep[direction];
                    if (nextRow < 0 || nextRow >= rows ||
                        nextColumn < 0 || nextColumn >= columns ||
                        dust[nextRow][nextColumn] == -1) {
                        continue;
                    }
                    change[nextRow][nextColumn] += spread;
                    ++neighbors;
                }
                change[row][column] -= spread * neighbors;
            }
        }

        for (int row = 0; row < rows; ++row) {
            for (int column = 0; column < columns; ++column) {
                dust[row][column] += change[row][column];
            }
        }

        for (int row = upper - 1; row > 0; --row) dust[row][0] = dust[row - 1][0];
        for (int column = 0; column + 1 < columns; ++column) {
            dust[0][column] = dust[0][column + 1];
        }
        for (int row = 0; row < upper; ++row) {
            dust[row][columns - 1] = dust[row + 1][columns - 1];
        }
        for (int column = columns - 1; column > 1; --column) {
            dust[upper][column] = dust[upper][column - 1];
        }
        dust[upper][1] = 0;

        for (int row = lower + 1; row + 1 < rows; ++row) {
            dust[row][0] = dust[row + 1][0];
        }
        for (int column = 0; column + 1 < columns; ++column) {
            dust[rows - 1][column] = dust[rows - 1][column + 1];
        }
        for (int row = rows - 1; row > lower; --row) {
            dust[row][columns - 1] = dust[row - 1][columns - 1];
        }
        for (int column = columns - 1; column > 1; --column) {
            dust[lower][column] = dust[lower][column - 1];
        }
        dust[lower][1] = 0;
    }

    int total = 0;
    for (const auto& row : dust) {
        for (int amount : row) {
            if (amount > 0) total += amount;
        }
    }
    cout << total << '\n';
    return 0;
}