AtCoder-Solutions/contest/contest1/4.cpp at main · LSUDOKO/AtCoder-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <bits/stdc++.h>
using namespace std;

struct cell {
    int row, col;
};

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

    int h, w;
    cin >> h >> w;

    vector<string> grid(h);
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
    }

    int drow[4] = {-1, 0, 1, 0};
    int dcol[4] = {0, 1, 0, -1};


    vector<vector<int>> is_black(h, vector<int>(w, 0));
    int total_black = 0;

    queue<cell> work_queue;


    for (int r = 0; r < h; r++) {
        for (int c = 0; c < w; c++) {
            if (grid[r][c] == '#') {
                is_black[r][c] = 1;
                total_black++;


                for (int k = 0; k < 4; k++) {
                    int nr = r + drow[k];
                    int nc = c + dcol[k];
                    if (nr >= 0 && nr < h && nc >= 0 && nc < w && grid[nr][nc] == '.') {
                        work_queue.push({nr, nc});
                    }
                }
            }
        }
    }

    while (!work_queue.empty()) {
        vector<cell> to_flip;
        set<pair<int,int>> next_candidates;


        while (!work_queue.empty()) {
            cell cur = work_queue.front();
            work_queue.pop();

            if (is_black[cur.row][cur.col]) continue;

            int black_neighbors = 0;
            for (int k = 0; k < 4; k++) {
                int nr = cur.row + drow[k];
                int nc = cur.col + dcol[k];
                if (nr >= 0 && nr < h && nc >= 0 && nc < w && is_black[nr][nc]) {
                    black_neighbors++;
                }
            }

            if (black_neighbors == 1) {
                to_flip.push_back(cur);
            }
        }


        for (auto cell : to_flip) {
            is_black[cell.row][cell.col] = 1;
            total_black++;


            for (int k = 0; k < 4; k++) {
                int nr = cell.row + drow[k];
                int nc = cell.col + dcol[k];
                if (nr >= 0 && nr < h && nc >= 0 && nc < w && !is_black[nr][nc]) {
                    next_candidates.insert({nr, nc});
                }
            }
        }


        for (auto [r, c] : next_candidates) {
            work_queue.push({r, c});
        }
    }

    cout << total_black <<endl;
    return 0;
}