oj.uz

Submission #754794

# Submission time Handle Problem Language Result Execution time Memory
754794 2023-06-08T14:24:03 Z __Davit__ Dijamant (COCI22_dijamant) C++17
70 / 70
 850 ms 280212 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<char>> maze;
vector<vector<int>> col;
int id = 1;
vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
vector<int> dy = {0, 1, -1, 0, 1, -1, 1, -1};


vector<pair<int, int>> coords;

bool valid(int x, int y) {
    if (x < 0 || x > n - 1 || y < 0 || y > m - 1) return false;

    if (maze[x][y] == '#')return false;
    if (col[x][y])return false;
    return true;
}


void dfs(int x, int y) {
    col[x][y] = id;
    coords.push_back({x, y});

    for (int i = 0; i < 4; i++) {
        if (valid(x + dx[i], y + dy[i])) dfs(x + dx[i], y + dy[i]);
    }
}

bool ok(const vector<pair<int, int>> &coords) {
    int left = m - 1, right = 0, up = n - 1, down = 0;
    for (auto [x, y]: coords) {
        left = min(left, y);
        right = max(right, y);
        up = min(up, x);
        down = max(down, x);
    }
    if (left == 0 || right == m - 1 || up == 0 || down == n - 1) {
        return false;
    }
    map<pair<int, int>, int> exists;
    pair<int, int> node{-1, -1};
    int cnt = 0;
    for (auto [x, y]: coords) {
        exists[{x, y}] = 1;
        if (up == x) {
            if (node.first != -1) {
                return 0;
            }
            node = {x, y};
        }
        cnt++;
    }
    int rowlength = 1;
    int cnt2 = 0;
    if (node.first != up) {
        return 0;
    }
    if ((down - up + 1) % 2 == 0)return false;
    for (int i = up; i <= up + (down - up + 1) / 2; i++) {
        for (int j = 0; j < rowlength; j++) {
            if (!exists[{node.first, node.second + j}]) {
                return 0;
            }
            cnt2++;
        }
        rowlength += 2;
        node.first++;
        node.second--;
//        assert(node.second >= 0);
    }
    node.second += 2;
    rowlength -= 4;
    for (int i = up + (down - up + 1) / 2 + 1; i <= down; i++) {
        for (int j = 0; j < rowlength; j++) {
            if (!exists[{node.first, node.second + j}]) {
                return 0;
            }
            cnt2++;
        }
        rowlength -= 2;
        node.first++;
        node.second++;
    }

    if (cnt2 != cnt) {
        return 0;
    }
    return 1;

}

int main() {
//    freopen("../input.txt", "r", stdin);

    cin >> n >> m;
    maze = vector<vector<char>>(n, vector<char>(m));
    col = vector<vector<int>>(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)cin >> maze[i][j];
    }


    int cnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (valid(i, j)) {
                coords.clear();
                dfs(i, j);
                if (ok(coords)) {
                    cnt++;
                }
                id++;
            }
        }
    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cout << (char) ('a' + col[i][j]);
//        }
//        cout << endl;
//    }

    cout << cnt << endl;

}


//11 17
//.................
//.................
//.................
//.................
//........#........
//.......#.#.......
//......#.##.......
//......#...#......
//......#.##.......
//.......#.........
//.................



//11 17
//.................
//........#........
//#......###.......
//.#....##.##......
//#....##...##.....
//......##.##......
//......####.......
//.....#..##.......
//......#.#........
//.......#.........
//.................

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 1 ms 304 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 445 ms 280212 KB Output is correct
15 Correct 239 ms 22536 KB Output is correct
16 Correct 439 ms 20828 KB Output is correct
17 Correct 431 ms 217156 KB Output is correct
18 Correct 273 ms 23584 KB Output is correct
19 Correct 607 ms 66308 KB Output is correct
20 Correct 850 ms 62808 KB Output is correct
21 Correct 697 ms 50652 KB Output is correct
22 Correct 692 ms 33672 KB Output is correct
23 Correct 741 ms 32124 KB Output is correct
24 Correct 767 ms 34588 KB Output is correct
25 Correct 456 ms 251324 KB Output is correct
26 Correct 343 ms 20684 KB Output is correct