Submission #749393

#	Time	Username	Problem	Language	Result	Execution time	Memory
749393		__Davit__	Dijamant (COCI22_dijamant)	C++17	0 / 70	2 ms	1108 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 qanak = 0;
    for (auto [x, y]: coords) {
        exists[{x, y}] = 1;
        if (up == x) {
            if (node.first != -1)return 0;
            node = {x, y};
        }
        qanak++;
    }
    int ln = 1;
    int qanak2 = 0;
//    if (node.first != up)return 0;
    for (int i = up; i <= up + (down - up + 1) / 2; i++) {
        for (int j = 0; j < ln; j++) {
            if (!exists[{node.first, node.second + j}])return 0;
            qanak2++;
        }
        ln += 2;
        node.first++;
        node.second--;
//        if (node.second < 0)return 0;
    }
    ln -= 2;
    for (int i = up + (down - up + 1) / 2 + 1; i <= down; i++) {
//        if (node.first != down)return 0;
        for (int j = 0; j < ln; j++) {
            if (!exists[{node.first, node.second + j}])return 0;
            qanak2++;
        }
        ln -= 2;
        node.first++;
        node.second++;
    }

//    if (qanak2 != qanak)return 0;
//    cout << "--------" << id << endl;
    return 1;

}

int main() {

    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++;
//                else cout << i << " " << j << endl;
                id++;
            }
        }
    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cout << col[i][j];
//        }
//        cout << endl;
//    }

    cout << cnt << endl;

}


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



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

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