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.
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; }
Коментарі