#include <bits/stdc++.h>
using namespace std;
const int dx[] = {1,-1, 0, 0};
const int dy[] = {0, 0, 1,-1};
int main() {
int h, w;
cin >> h >> w;
vector<string> temp(h);
for (auto& s: temp) cin >> s;
vector< vector<int> > graph(h + 2, vector<int>(w + 2, -1));
vector< vector<int> > visited(h + 2, vector<int>(w + 2, 0));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (temp[i][j] == '#') {
graph[i + 1][j + 1] = 1;
} else {
graph[i + 1][j + 1] = 0;
}
}
}
set< pair<int, int> > s;
int white = 0, black;
for (int i = 1; i <= 1000; i++) {
s.insert({white, 4 * i});
white += 4 * i;
}
int ans = 0;
int tried = 0;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (visited[i][j]) continue;
white = black = 0;
queue<pair<int, int> > q;
q.push({i, j});
visited[i][j] = ++tried;
int ny, nx;
bool flag = 1;
while (q.size()) {
auto& [y, x] = q.front();
for (int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if (visited[ny][nx] >= tried) continue;
visited[ny][nx] = tried;
if (graph[ny][nx] < 0) {
flag = 0;
} else {
if (graph[ny][nx] == 1) black++;
if (graph[ny][nx] == 0) {
white++;
q.push({ny, nx});
}
}
}
// cerr << q.size() << '\n';
q.pop();
}
// cerr << white << ' ' << black << '\n';
// cerr << i << ", " << j << '\n';
if (flag && s.find({white, black}) != s.end()) {
// cerr << "-----\n";
ans++;
}
}
}
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:48:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | auto& [y, x] = q.front();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
