Submission #754794

#	Time	Username	Problem	Language	Result	Execution time	Memory
754794		__Davit__	Dijamant (COCI22_dijamant)	C++17	70 / 70	850 ms	280212 KiB

Main

#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 / 20
• Subtask 2: 50 / 50