oj.uz

답안 #631574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631574 2022-08-18T08:56:30 Z GudStonks Dijamant (COCI22_dijamant) C++17
70 / 70
 861 ms 15628 KB 
#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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 496 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 508 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 496 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 508 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 167 ms 11260 KB Output is correct
15 Correct 81 ms 11020 KB Output is correct
16 Correct 384 ms 10908 KB Output is correct
17 Correct 175 ms 11132 KB Output is correct
18 Correct 279 ms 15628 KB Output is correct
19 Correct 155 ms 10828 KB Output is correct
20 Correct 181 ms 15620 KB Output is correct
21 Correct 158 ms 10632 KB Output is correct
22 Correct 258 ms 11424 KB Output is correct
23 Correct 207 ms 10616 KB Output is correct
24 Correct 238 ms 11536 KB Output is correct
25 Correct 167 ms 10712 KB Output is correct
26 Correct 861 ms 10864 KB Output is correct