Submission #1219462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219462		khzh	Zoo (COCI19_zoo)	C++20	110 / 110	41 ms	5444 KiB

zoo

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1005;
const int MOD = 1e9 + 7;
const ll oo = 1e18;

#define fi first
#define se second
#define pb push_back

char a[N][N];
int vs[N][N];
int n, m;
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};

int c[256];
int cur, ans;

void inp(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
}

void process(void) {
    c['T'] = 0;
    c['B'] = 1;
    cur = c[a[1][1]];

    queue<pair<int,int>> q, nq;
    vs[1][1] = 1;
    q.push({1,1});
    ans = 0;

    while (!q.empty()) {
        ans++;
        while (!q.empty()) {
            auto [x,y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (vs[nx][ny]) continue;
                if (a[nx][ny] != 'B' && a[nx][ny] != 'T') continue;
                vs[nx][ny] = 1;
                if (c[a[nx][ny]] == cur) q.push({nx, ny});
                else nq.push({nx, ny});
            }
        }
        cur = !cur;
        q = nq;
        while (!nq.empty()) nq.pop();
    }

    cout << ans;
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    
    inp();
    process();
    return 0;
}

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