#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 2100;
int n, m, up_down[N][N], left_right[N][N];
char c[N][N];
int d1[2 * N][N], d2[2 * N][N], ans, diag1[N][N], diag2[N][N];
bool good1(int x, int y, int x1, int y1)
{
while(x != x1 || y != y1)
{
if (c[x][y] != '#') return 0;
x++; y++;
}
return 1;
}
bool good2(int x, int y, int x1, int y1)
{
while(x != x1 || y != y1)
{
if (c[x][y] != '#') return 0;
x--; y++;
}
return 1;
}
bool good(int x1, int y1, int x2, int y2)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if (i > x1 && i < x2 && j > y1 && j < y2 && c[i][j] == '#')
{
cout << i << ' ' << j << ' ' << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
return 0;
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> c[i][j];
for(int i = 1; i <= n; i++)
{
int lst = -1e9;
for(int j = 1; j <= m; j++)
{
if (c[i][j] == '#') lst = j;
left_right[i][j] = j - lst;
}
lst = 1e9;
for(int j = m; j >= 1; j--)
{
if (c[i][j] == '#') lst = j;
left_right[i][j] = min(left_right[i][j], lst - j);
}
}
for(int j = 1; j <= m; j++)
{
int lst = -1e9;
for(int i = 1; i <= n; i++)
{
if (c[i][j] == '#') lst = i;
up_down[i][j] = i - lst;
}
lst = 1e9;
for(int i = n; i >= 1; i--)
{
if (c[i][j] == '#') lst = i;
up_down[i][j] = min(up_down[i][j], lst - i);
}
}
for(int j = 1; j <= n; j++)
{
int lst = -1e9;
int x = j, y = 1;
for(int skok = 1; x >= 1 && y <= m; x--, y++, skok++)
{
if (c[x][y] == '#') lst = skok;
diag1[x][y] = skok - lst;
}
lst = -1e9;
x++; y--;
for(int skok = 1; x <= n && y >= 1; x++, y--, skok++)
{
if (c[x][y] == '#') lst = skok;
diag1[x][y] = min(diag1[x][y], skok - lst);
}
}
for(int j = 1; j <= m; j++)
{
int lst = -1e9;
int x = n, y = j;
for(int skok = 1; x >= 1 && y <= m; x--, y++, skok++)
{
if (c[x][y] == '#') lst = skok;
diag1[x][y] = skok - lst;
}
lst = -1e9;
x++; y--;
for(int skok = 1; x <= n && y >= 1; x++, y--, skok++)
{
if (c[x][y] == '#') lst = skok;
diag1[x][y] = min(diag1[x][y], skok - lst);
}
}
for(int j = 1; j <= n; j++)
{
int lst = -1e9;
int x = j, y = 1;
for(int skok = 1; x <= n && y <= m; x++, y++, skok++)
{
if (c[x][y] == '#') lst = skok;
diag2[x][y] = skok - lst;
}
lst = -1e9;
x--; y--;
for(int skok = 1; x >= 1 && y >= 1; x--, y--, skok++)
{
if (c[x][y] == '#') lst = skok;
diag2[x][y] = min(diag2[x][y], skok - lst);
}
}
for(int j = 1; j <= m; j++)
{
int lst = -1e9;
int x = 1, y = j;
for(int skok = 1; x <= n && y <= m; x++, y++, skok++)
{
if (c[x][y] == '#') lst = skok;
diag2[x][y] = skok - lst;
}
lst = -1e9;
x--; y--;
for(int skok = 1; x >= 1 && y >= 1; x--, y--, skok++)
{
if (c[x][y] == '#') lst = skok;
diag2[x][y] = min(diag2[x][y], skok - lst);
}
}
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cout << i << ' ' << j << ' ' << diag2[i][j] << endl;
}
*/
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if (up_down[i][j] > n + m) up_down[i][j] = 1e9;
if (left_right[i][j] > n + m) left_right[i][j] = 1e9;
}
*/
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
//int d = 0;
int d = min({up_down[i][j], left_right[i][j], diag1[i][j] * 2, diag2[i][j] * 2});
if (d == 0) continue;
if (i - d <= 0 || i + d > n || j + d > m || j - d <= 0) continue;
if (c[i - d][j] != '#' || c[i + d][j] != '#' || c[i][j - d] != '#' || c[i][j + d] != '#') continue;
if (good1(i - d, j, i, j + d) && good1(i, j - d, i + d, j) && good2(i + d, j, i, j + d) && good2(i, j - d, i - d, j))
{
ans++;
}
}
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2004 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2052 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
2260 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2004 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2052 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
2260 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
