Submission #1262179

#TimeUsernameProblemLanguageResultExecution timeMemory
1262179dhuyyyyDijamant (COCI22_dijamant)C++20
0 / 70
1 ms1344 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 2005;
const int INF = 1e9;
const int MOD = 998244353;

int n,m,cnt,res = 0;
ii mx,mn;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool vis[N][N];
char a[N][N];

bool ok(int i,int j){
    return i >= 1 && i <= n && j >= 1 && j <= m && a[i][j] == '.' && !vis[i][j];
}
bool ok2(int i,int j){
    return i > 1 && i < n && j > 1 && j < m;
}
void dfs(int i,int j){
    vis[i][j] = 1;
    cnt++;
    mx = {max(mx.fi,i+j),max(mx.se,i-j)};
    mn = {min(mn.fi,i+j),min(mn.se,i-j)};
    for (int k = 0; k < 4; k++){
        int x = i + dx[k];
        int y = j + dy[k];
        if (ok(x,y)) dfs(x,y);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] == '.' && !vis[i][j]){
                cnt = 0;
                mx = {-1e9,-1e9};
                mn = {1e9,1e9};
                dfs(i,j);
                int tmp = (mx.fi - mn.fi) / 2 + 1;
                res += (ok2(i,j) && (mx.fi - mn.fi) % 2 == 0 && tmp * tmp + (tmp - 1) * (tmp - 1) == cnt && mx.se - mn.se == mx.fi - mn.fi);
            }
        }
    }
    cout << res;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...