Submission #1267571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267571		vk3601h	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1218 ms	112068 KiB

tracks

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int H, W;
    cin >> H >> W;

    vector<string> grid(H);
    for (int i = 0; i < H; ++i) cin >> grid[i];

    deque<pair<int, int>> frontier;
    vector<vector<int>> dist(H, vector<int>(W, INT_MAX));

    auto next_node = [&](const pair<int, int> &node) -> vector<pair<int, int>>{
        vector<pair<int, int>> nxt;
        if (node.first > 0) nxt.push_back({node.first - 1, node.second});
        if (node.first < H - 1) nxt.push_back({node.first + 1, node.second});
        if (node.second > 0) nxt.push_back({node.first, node.second - 1});
        if (node.second < W - 1) nxt.push_back({node.first, node.second + 1});
        return nxt;
    };

    frontier.push_back({0, 0});
    dist[0][0] = 0;
    while (!frontier.empty()){
        pair<int, int> u = frontier.front();
        frontier.pop_front();
        for (pair<int, int> v : next_node(u)){
            if (grid[v.first][v.second] == '.') continue;
            if (grid[v.first][v.second] == grid[u.first][u.second]){
                if (dist[u.first][u.second] < dist[v.first][v.second]){
                    dist[v.first][v.second] = dist[u.first][u.second];
                    frontier.push_front(v);
                }
            }
            else {
                if (dist[u.first][u.second] + 1 < dist[v.first][v.second]){
                    dist[v.first][v.second] = dist[u.first][u.second] + 1;
                    frontier.push_back(v);
                }
            }
        }
    }

    int ans = 0;
    for (int r = 0; r < H; ++r){
        for (int c = 0; c < W; ++c){
            if (dist[r][c] != INT_MAX){
                ans = max(ans, dist[r][c]);
            }
        }
    }

    cout << ans + 1;
    return 0;
}

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