Submission #1246762

#TimeUsernameProblemLanguageResultExecution timeMemory
1246762vht2025Dijamant (COCI22_dijamant)C++20
70 / 70
124 ms40844 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...