#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #include<bits/extc++.h>
//__gnu_pbds
bool arr[2005][2005];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
bool inbound(int x, int y) {
return (x >= 0 && y >= 0);
}
int xpymax, xpymin, xmymax, xmymin;
int cnt = 0;
void dfs(int x, int y) {
arr[x][y] = 1;
cnt++;
xpymax = max(xpymax, x + y);
xpymin = min(xpymin, x + y);
xmymax = max(xmymax, x - y);
xmymin = min(xmymin, x - y);
for (int i = 0; i < 4; i++) {
if (inbound(x + dx[i], y + dy[i])) {
if (arr[x + dx[i]][y + dy[i]] == 0) {
dfs(x + dx[i], y + dy[i]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < 2005; i++) {
arr[i][m + 4] = 1;
arr[n + 4][i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char a;
cin >> a;
if (a == '#') arr[i][j] = 1;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!arr[i][j]) {
xpymax = INT_MIN;
xpymin = INT_MAX;
xmymax = INT_MIN;
xmymin = INT_MAX;
cnt = 0;
dfs(i, j);
// cout<<i<<" "<<j<<"\n";
// cout<<xpymax<<" "<<xpymin<<" "<<xmymax<<' '<<xmymin<<" "<<cnt<<"\n";
if (xpymax - xpymin != xmymax - xmymin || (xpymax - xpymin) % 2) continue;
int l = (xpymax - xpymin) / 2 + 1;
int area = (2 * l * l) - (2 * l) + 1;
// cout<<area<<"\n";
if (cnt == area) {
ans++;
}
}
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4312 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4312 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
237 ms |
238160 KB |
Output is correct |
| 15 |
Correct |
33 ms |
8016 KB |
Output is correct |
| 16 |
Correct |
90 ms |
8528 KB |
Output is correct |
| 17 |
Correct |
135 ms |
118544 KB |
Output is correct |
| 18 |
Correct |
47 ms |
8784 KB |
Output is correct |
| 19 |
Correct |
75 ms |
35088 KB |
Output is correct |
| 20 |
Correct |
115 ms |
51964 KB |
Output is correct |
| 21 |
Correct |
84 ms |
41808 KB |
Output is correct |
| 22 |
Correct |
79 ms |
16724 KB |
Output is correct |
| 23 |
Correct |
80 ms |
23824 KB |
Output is correct |
| 24 |
Correct |
90 ms |
22096 KB |
Output is correct |
| 25 |
Correct |
181 ms |
172624 KB |
Output is correct |
| 26 |
Correct |
45 ms |
8284 KB |
Output is correct |
