Submission #332533

#	Time	Username	Problem	Language	Result	Execution time	Memory
332533		Ciafrino	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	623 ms	131048 KiB

tracks

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

int main() {
    cout.tie(nullptr)->sync_with_stdio(false);
    int H, W; cin >> H >> W;

    vector<string> grid(H);
    for (string& S : grid) cin >> S;

    vector<vector<int>> mindist(H, vector<int>(W, -1));
    deque<array<int, 2>> bfs = {{0, 0}};
    vector<int> dx = {1, 0, -1, 0};
    vector<int> dy = {0, 1, 0, -1};

    auto check = [&](int a, int b) -> bool {
        if (a < 0 || a >= H || b < 0 || b >= W || grid[a][b] == '.') return false;
        return true;
    };

    mindist[0][0] = 1;
    int res = 0;
    while (!bfs.empty()) {
        auto [u, v] = bfs.front();
        bfs.pop_front();
        res = max(res, mindist[u][v]);
        for (int d = 0; d < 4; ++d) {
            int a = u + dx[d], b = v + dy[d];
            if (!check(a, b)) continue;
            if (mindist[a][b] == -1) {
                int prev = mindist[u][v];
                if (grid[u][v] == grid[a][b]) {
                    mindist[a][b] = prev;
                    bfs.push_front({a, b});
                } else {
                    mindist[a][b] = 1 + prev;
                    bfs.push_back({a, b});
                }
            }
        }
    }

    cout << res << '\n';
}

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