Submission #234273

#	Time	Username	Problem	Language	Result	Execution time	Memory
234273		jungsnow	Zoo (COCI19_zoo)	C++14	45 / 110	2088 ms	10072 KiB

zoo

#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int, int> ii;

const int N = 1015;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

char C[N][N];
int n, m;
bool vist[N][N];

inline bool check(int r, int c) {
    return (r > 0 && r <= n && c > 0 && c <= m && C[r][c] == C[1][1] && !vist[r][c]);
}

inline char other(char c) {
    if (c == 'T') return 'B';
    return 'T';
}

int flood_fill() {
    vector< ii > v;
    queue< ii > q;
    q.push({1, 1});
    vist[1][1] = 1;
    while (q.size()) {
        ii cur = q.front();
        q.pop();
        v.push_back(cur);
        for (int i = 0; i < 4; i++) {
            int u = cur.fi + dx[i];
            int v = cur.se + dy[i];
            if (check(u, v)) {
                q.push({u, v});
                vist[u][v] = 1;
            }
        }
    }

    char c = other(C[1][1]);
    for (auto &p : v) {
        C[p.fi][p.se] = c;
        vist[p.fi][p.se] = 0;
    }
    return v.size();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    int cn = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> C[i][j];
            cn += (C[i][j] != '*');
        }
    }
    int sol = 1;
    while (flood_fill() < cn) ++sol;
    cout << sol;
    return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 0 / 65