제출 #631574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631574		GudStonks	Dijamant (COCI22_dijamant)	C++17	70 / 70	861 ms	15628 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, ans;
string s[2005];
queue<pair<int, int> >q;
bool us[2005][2005];
pair<int, int>dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void fun()
{
    cin>>n>>m;
    for(int i = 0; i < n; i++)
    {
        cin>>s[i];
    }
    for(int i = 1; i < n - 1; i++)
    {
        for(int j = 1; j < m - 1; j++)
        {
            if(!us[i][j] && s[i][j] == '.')
            {
                vector<int>xx(n + 1, 0), yy(m + 1, 0);
                q.push({i, j});
                bool boo = 0;
                int c = 0;
                while(!q.empty())
                {
                    int x = q.front().first, 
                        y = q.front().second;
                    q.pop();
                    us[x][y] = 1;
                    bool goo = 0;
                    for(int k = 0; k < 4; k++)
                    {
                        if(x + dir[k].first > n - 1 
                            || x + dir[k].first < 0 
                            || y + dir[k].second > m - 1 
                            || y + dir[k].second < 0)
                        {
                            boo = 1;
                            continue;
                        }
                        if(s[x + dir[k].first][y + dir[k].second] == '#')
                            goo = 1;
                        else if(!us[x + dir[k].first][y + dir[k].second] &&
                                s[x + dir[k].first][y + dir[k].second] == '.')
                            q.push({x + dir[k].first, y + dir[k].second}),
                            us[x + dir[k].first][y + dir[k].second] = 1;
                    }
                    if(goo)
                        xx[x] += 10000 + y, yy[y] += 10000 + x, c++;
                }
                if(boo)
                    continue;
                if(c == 1)
                {
                    ans++;
                    continue;
                }
                int l = 0, x1, x2, y1, y2;
                while(l < n - 1 && xx[l] / 10000 == 0)
                    l++;
                if(xx[l] / 10000 != 1 || xx[l + 1] / 10000 != 2)
                    continue;
                x1 = xx[l];
                l++;
                int tt = 0;
                while(l < n - 1 && xx[l] / 10000 == 2)
                    l++, tt++;
                if(xx[l] / 10000 != 1 || (l != n - 1 && xx[l + 1] / 10000 != 0))
                    continue;
                x2 = xx[l];
                l = 0;
                while(l < m - 1 && yy[l] / 10000 == 0)
                    l++;
                if(yy[l] / 10000 != 1 || yy[l + 1] / 10000 != 2)
                    continue;
                y1 = yy[l];
                l++;
                while(l < m - 1 && yy[l] / 10000 == 2)
                    l++;
                if(yy[l] / 10000 != 1 || (l != m - 1 && yy[l + 1] / 10000 != 0) || tt % 2 == 0)
                    continue;
                y2 = yy[l];
                if((x1 % 10000) != (x2 % 10000) || (y1 % 10000) != (y2 % 10000))
                    continue;
                ans++;
            }
        }
    }
    cout<<ans;
}

int main()
{
	ll ttt = 1;
	//cin>>ttt;
	while(ttt--)
		fun();
}

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