Submission #1246761

#TimeUsernameProblemLanguageResultExecution timeMemory
1246761vht2025Dijamant (COCI22_dijamant)C++20
0 / 70
1 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int DR[4]={-1,1,0,0}, DC[4]={0,0,-1,1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; if(!(cin>>n>>m)) return 0;
    vector<string> g(n); for(string &s:g) cin>>s;
    vector<vector<char>> vis(n, vector<char>(m,0));
    long long ans = 0;
    for(int r=0;r<n;++r)for(int c=0;c<m;++c)if(g[r][c]=='.'&&!vis[r][c]){
        queue<pii> q; q.push({r,c}); vis[r][c]=1;
        long long cnt = 0;
        int a=INT_MAX,b=INT_MIN,c2=INT_MAX,d=INT_MIN;   // diag bounds
        while(!q.empty()){
            auto [x,y]=q.front(); q.pop();
            ++cnt;
            int p=x+y, q2=x-y;
            a=min(a,p); b=max(b,p);
            c2=min(c2,q2); d=max(d,q2);
            for(int k=0;k<4;++k){
                int nx=x+DR[k], ny=y+DC[k];
                if(nx>=0&&nx<n&&ny>=0&&ny<m && g[nx][ny]=='.' && !vis[nx][ny]){
                    vis[nx][ny]=1; q.push({nx,ny});
                }
            }
        }
        int s=b-a;                    // candidate size
        if(s>0 && s==d-c2 && cnt==1LL*s*s+1LL*(s-1)*(s-1))
            ++ans;
    }
    cout<<ans<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...