Submission #1294395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294395		Balsa	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	315 ms	33952 KiB

tracks

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

#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using ll = long long;

ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
bool vis[4005][4005];

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<string> a(n);
    bool R = false, F = false;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        for (char c : a[i]) {
            if (c == 'R') R = true;
            if (c == 'F') F = true;
        }
    }
    
    auto bfs = [&](ll xs, ll ys, char c) {
        queue<pair<ll, ll>> q;
        q.push({xs, ys});
        vis[xs][ys] = 1;

        while (!q.empty()) {
            auto[x, y] = q.front();
            q.pop();

            for (ll i = 0; i < 4; i++) {
                ll nx = x + dx[i];
                ll ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (vis[nx][ny] || a[nx][ny] != c) continue;

                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    };

    ll cnt = 0;
    char c = a[0][0];
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            if (a[i][j] != c || vis[i][j]) continue;
            bfs(i, j, c);
            cnt++;
        }
    }

    cout << cnt + (F && R) << '\n';
}

int main() {
    // freopen("walk.in", "r", stdin);
    // freopen("walk.out", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70