Submission #1161414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161414		uakkes	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	500 ms	80956 KiB

tracks

//
// All truth are easy to understand once they are discovered.
// The point is to discover them
//
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 123;
int was[4001][4001];

void solve(){
    int n, m; cin >> n >> m;
    string g[n];
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }

    int f = 0, r = 0;
    vector<int> dx = {0, 0, 1, -1};
    vector<int> dy = {1, -1, 0, 0};
    auto bfs = [&](int xx, int yy, char t) {
        if (t == 'F') f++;
        else r++;
        queue<pair<int, int>> q;
        q.emplace(xx, yy);

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

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

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                was[nx][ny] == 0 && g[nx][ny] == g[x][y]) {
                    was[nx][ny] = 1;
                    q.emplace(nx, ny);
                }
            }
        }
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!was[i][j] && g[i][j] != '.') {
                bfs(i, j, g[i][j]);
            }
        }
    }
    // cout << f << ' ' << r;
    cout << min(f, r) + 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
//    cin >> tt;

    while (tt--) {
        solve();
        cout << '\n';
    }

    return 0;
}

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