#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<char>> maze;
vector<vector<int>> col;
int id = 1;
vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
vector<int> dy = {0, 1, -1, 0, 1, -1, 1, -1};
vector<pair<int, int>> coords;
bool valid(int x, int y) {
if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
return false;
}
if (maze[x][y] == '#')return false;
if (col[x][y])return false;
return true;
}
void dfs(int x, int y) {
col[x][y] = id;
coords.push_back({x, y});
for (int i = 0; i < 4; i++) {
if (valid(x + dx[i], y + dy[i])) {
dfs(x + dx[i], y + dy[i]);
}
}
}
bool ok(const vector<pair<int, int>> &coords) {
int left = m - 1, right = 0, up = n - 1, down = 0;
for (auto [x, y]: coords) {
left = min(left, y);
right = max(right, y);
up = min(up, x);
down = max(down, x);
}
if (left == 0 || right == m - 1 || up == 0 || down == n - 1)return false;
// sort(coords.begin(), coords.end(), [&](pair<int, int> a, pair<int, int> b) {
// return (tie(a.second, a.first) < tie(b.second, b.first));
// });
map<int, int> mmm;
for (auto [x, y]: coords) mmm[y]++;
vector<int> d;
for (auto x: mmm) d.push_back(x.second);
int cur = 1;
for (int i = 0; i <= (int) d.size() / 2; i++) {
if (d[i] != cur)return 0;
cur += 2;
}
cur -= 4;
for (int i = (int) d.size() / 2 + 1; i < (int) d.size(); i++) {
if (d[i] != cur)return 0;
cur -= 2;
}
return 1;
}
int main() {
cin >> n >> m;
maze = vector<vector<char>>(n, vector<char>(m));
col = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)cin >> maze[i][j];
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (valid(i, j)) {
coords.clear();
dfs(i, j);
if (ok(coords))cnt++;
// else cout << i << " " << j << endl;
id++;
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << col[i][j] << "\t";
// }
// cout << endl;
// }
cout << cnt << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
