Submission #749391

#	Time	Username	Problem	Language	Result	Execution time	Memory
749391		__Davit__	Dijamant (COCI22_dijamant)	C++17	0 / 70	1 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;



//    sort(coords.begin(), coords.end(), [&](pair<int, int> a, pair<int, int> b) {
//        return (tie(a.second, a.first) < tie(b.second, b.first));
//    });

    map<int, int> mmm;
    for (auto [x, y]: coords) mmm[y]++;

    vector<int> d;
    for (auto x: mmm) d.push_back(x.second);
    int cur = 1;
    for (int i = 0; i <= (int) d.size() / 2; i++) {
        if (d[i] != cur)return 0;
        cur += 2;
    }
    cur -= 4;
    for (int i = (int) d.size() / 2 + 1; i < (int) d.size(); i++) {
        if (d[i] != cur)return 0;
        cur -= 2;
    }
    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] << "\t";
//        }
//        cout << endl;
//    }

    cout << cnt << endl;

}

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