Editorial for 2182: Фарбування клітинок


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int table[1000][1000], n, m;
vector < pair < int, int> > st;

int sumSquare(int i, int j)
{
    return table[i][j] + table[i + 1][j] + table[i][j + 1] + table[i + 1][j + 1];
}
void pushSquare(int i, int j)
{
    if ((0 <= i) && (i < n - 1) && (0 <= j) && (j < m - 1))
        if (sumSquare(i, j) == 3)
            st.push_back(make_pair(i, j));
}

void pushNeighbors(int i, int j)
{
    pushSquare(i - 1, j - 1);
    pushSquare(i, j - 1);
    pushSquare(i - 1, j);
    pushSquare(i, j);
}
void updTile(int i, int j)
{
    if ((0 <= i) && (i < n) && (0 <= j) && (j < m))
        if (!table[i][j])
            table[i][j] = 1;
            pushNeighbors(i, j);
}

void updSquare(int i, int j)
{
    updTile(i, j);
    updTile(i + 1, j);
    updTile(i, j + 1);
    updTile(i + 1, j + 1);
}

int main()
{
    //freopen("e.in", "r", stdin);
    //freopen("e.out", "w", stdout);
    cin >> n >> m;
    char c;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> c;
            if (c == '#')
                table[i][j] = 1;
        }
    }
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++)
            if (sumSquare(i, j) == 3)
                st.push_back(make_pair(i, j));
    while (!st.empty())
    {
        pair < int, int > p = st.back();
        st.pop_back();
        if (sumSquare(p.first, p.second))
            updSquare(p.first, p.second);
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            answer += table[i][j];
    cout << answer << endl;
    return 0;
}

Коментарі

Please read the guidelines before commenting.


Ще немає коментарів.