Submission #1246764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246764		vht2025	Dijamant (COCI22_dijamant)	C++20	70 / 70	126 ms	40844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
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(auto &s:g) cin>>s;

    vector<vector<char>> vis(n, vector<char>(m,0));
    long long ans = 0;

    for(int sr=0; sr<n; ++sr) for(int sc=0; sc<m; ++sc)
    if(g[sr][sc]=='.' && !vis[sr][sc]){
        // --- BFS ruột ---
        queue<pair<int,int>> q; q.push({sr,sc}); vis[sr][sc]=1;
        long long cnt = 0;
        int pmin=INT_MAX,pmax=INT_MIN,qmin=INT_MAX,qmax=INT_MIN;
        vector<pair<int,int>> inner;

        while(!q.empty()){
            auto [r,c]=q.front(); q.pop();
            inner.push_back({r,c});
            ++cnt;
            int p=r+c, qd=r-c;
            pmin=min(pmin,p); pmax=max(pmax,p);
            qmin=min(qmin,qd); qmax=max(qmax,qd);
            for(int k=0;k<4;++k){
                int nr=r+DR[k], nc=c+DC[k];
                if(nr>=0 && nr<n && nc>=0 && nc<m &&
                   g[nr][nc]=='.' && !vis[nr][nc]){
                    vis[nr][nc]=1; q.push({nr,nc});
                }
            }
        }

        int d1=pmax-pmin, d2=qmax-qmin;
        if(d1!=d2 || d1&1) continue;
        int R=d1/2+1;                 // bán kính biên
        if(cnt != 1LL*R*R + 1LL*(R-1)*(R-1)) continue;

        // tính tâm
        if(((pmin+pmax)&1) || ((qmin+qmax)&1)) continue; // lệch lưới
        int r0=((pmin+pmax)+(qmin+qmax))/4;
        int c0=(pmin+pmax)/2 - r0;
        if(r0<0||r0>=n||c0<0||c0>=m) continue;

        // --- kiểm tra biên ---
        bool ok=true;
        for(int dr=-R; ok && dr<=R; ++dr){
            int dc = R - abs(dr);
            for(int sgn:{-1,1}){
                int r=r0+dr, c=c0+sgn*dc;
                if(r<0||r>=n||c<0||c>=m || g[r][c]!='#'){ ok=false; break; }
            }
        }
        if(ok) ++ans;
    }
    cout<<ans<<"\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50