Submission #825946

#	Time	Username	Problem	Language	Result	Execution time	Memory
825946		vjudge1	Dijamant (COCI22_dijamant)	C++14	0 / 70	2 ms	4820 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=2e3+11;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0,  0, 1, -1};
bool a[N][N];
int m, n;
bool ch(int x, int y)
{
    return (x>=0 && y>=0);
}
int mi1, mi2, ma1, ma2, ans, cnt;
void dfs(int x, int y)
{
    a[x][y]=1;
    cnt++;
    ma1=max(ma1, x+y);
    mi1=min(mi1, x+y);
    ma2=max(ma2, x-y);
    mi2=min(mi1, x-y);
    for(int i=0;i<4;i++) if(ch(x+dx[i], y+dy[i])) if(a[x+dx[i]][y+dy[i]]==0) dfs(x+dx[i], y+dy[i]);
}
void sol()
{
    cin >> m >> n;
    for(int i=0;i<N-6;i++) a[i][n+4]=1, a[m+4][i]=1;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) {char x; cin >> x; a[i][j]=(x=='#');}
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==0)
            {
                ma1=ma2=-2e9;
                mi1=mi2=2e9;
                cnt=0;
                dfs(i, j);
                if(ma1-mi1 != ma2-mi2 || (ma1-mi1)%2) continue;
                int vlxx=(ma1-mi1)/2+1;
                int ss=(2*vlxx*vlxx)-(2*vlxx)+1;
                if(ss==cnt) ans++;
            }
        }
    }
    cout << ans;
}
signed main()
{
//    freopen("task.INP", "r", stdin);
//    freopen("task.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

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