제출 #1304638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304638		themariofan102	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	301 ms	20448 KiB

tracks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define solveT() {int t; cin >> t; while (t--) solve();};

#define int long long

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> arr(h);
    for (int i = 0; i < h; i++) {
        cin >> arr[i];
    }
    set<char> st;
    for (auto it : arr) {
        for (auto it2 : it) {
            if (it2 != '.')
                st.insert(it2);
        }
    }
    if (st.size() == 1) {
        cout << 1 << endl;
        return;
    }
    vector<pair<int, int>> dr = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    vector<vector<bool>> vis(h, vector<bool>(w, false));
    auto bfs = [&](int i, int j) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : dr) {
                if (x + dx >= 0 && x + dx < h && y + dy >= 0 && y + dy < w && arr[x + dx][y + dy] == arr[0][0] && !vis[x + dx][y + dy]) {
                    vis[x + dx][y + dy] = true;
                    q.emplace(x + dx, y + dy);
                }
            }
        }
    };
    int ans{1};
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (arr[i][j] == arr[0][0] && !vis[i][j]) {
                vis[i][j] = true;
                bfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    solve();
    return 0;
}

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