Submission #1337403

#TimeUsernameProblemLanguageResultExecution timeMemory
1337403neptunnsZoo (COCI19_zoo)C++20
0 / 110
4 ms8260 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define maxn 1005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first
vector<vector<int>> a(maxn, vector<int>(maxn, 0));
int n, m;

void bfs(int i, int j) {
    int last = a[i][j];
    queue<pair<int, int>> q;
    q.push({i, j});
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    while (!q.empty()) {
        int x = q.front().F, y = q.front().S;
        q.pop();
        if (a[x][y] != last) continue;
        a[x][y] = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (a[nx][ny] == last) {
                    q.push({nx, ny});
                }
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char x;
            cin >> x;
            if (x == 'T') {
                a[i][j] = 1;
                if ((i == 0 || a[i - 1][j] != 1) &&
                    (j == 0 || a[i][j - 1] != 1)) {
                    v.pb({i, j});
                }
            } else if (x == 'B') {
                a[i][j] = 2;
                if ((i == 0 || a[i - 1][j] != 2) &&
                    (j == 0 || a[i][j - 1] != 2)) {
                    v.pb({i, j});
                }
            }
        }
    }
    int ans = 0;
    for (auto [i, j] : v) {
        if (a[i][j] == 0) continue;
        bfs(i, j);
        ans++;
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...