#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;
}
map<pair<int, int>, int> exists;
pair<int, int> node{-1, -1};
int cnt = 0;
for (auto [x, y]: coords) {
exists[{x, y}] = 1;
if (up == x) {
if (node.first != -1) {
return 0;
}
node = {x, y};
}
cnt++;
}
int rowlength = 1;
int cnt2 = 0;
if (node.first != up) {
return 0;
}
for (int i = up; i <= up + (down - up + 1) / 2; i++) {
for (int j = 0; j < rowlength; j++) {
if (!exists[{node.first, node.second + j}]) {
return 0;
}
cnt2++;
}
rowlength += 2;
node.first++;
node.second--;
assert(node.second >= 0);
}
node.second += 2;
rowlength -= 4;
for (int i = up + (down - up + 1) / 2 + 1; i <= down; i++) {
for (int j = 0; j < rowlength; j++) {
if (!exists[{node.first, node.second + j}]) {
// cout << node.first << " " << node.second + j << endl;
return 0;
}
cnt2++;
}
rowlength -= 2;
node.first++;
node.second++;
}
if (cnt2 != cnt) {
return 0;
}
// cout << "--------" << id << endl;
return 1;
}
int main() {
// freopen("../input.txt", "r", stdin);
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++;
}
id++;
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << (char) ('a' + col[i][j]);
// }
// cout << endl;
// }
cout << cnt << endl;
}
//11 17
//.................
//.................
//.................
//.................
//.................
//.......#.........
//......#.##.......
//......#...#......
//......#.##.......
//.......#.........
//.................
//11 17
//.................
//.................
//.................
//.................
//.................
//.......#.........
//......#.#........
//.....#...#.......
//......#.#........
//.......#.........
//.................
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
2 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 |
- |
