Submission #706870

#	Time	Username	Problem	Language	Result	Execution time	Memory
706870		y_combinator	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	971 ms	265380 KiB

tracks

#include <algorithm>
#include <array>
#include <deque>
#include <ios>
#include <iostream>
#include <string>
#include <vector>

using std::array;
using std::cin;
using std::cout;
using std::deque;
using std::ios_base;
using std::max;
using std::max_element;
using std::string;
using std::vector;

using Location = array<int, 2>;

constexpr auto dir_1 = array<int, 4>({1, 0, -1, 0});
constexpr auto dir_2 = array<int, 4>({0, 1, 0, -1});

auto solve() {

    auto h = 0;
    auto w = 0;

    cin >> h >> w;

    auto map = vector<string>(h);

    for (auto& x : map) {
        cin >> x;
    }

    auto distances = vector<vector<int>>(h, vector<int>(w, -1));

    distances[0][0] = 0;

    auto parents = vector<vector<Location>>(h, vector<Location>(w, Location({-1, -1})));
    auto process = deque<Location>({Location({0, 0})});

    while (!process.empty()) {
        const auto front = process.front();
        process.pop_front();
        const auto& [row, col] = front;
        const auto [parent_row, parent_col] = parents[row][col];
        if (row || col) {
            distances[row][col] = (
                distances[parent_row][parent_col] + (map[row][col] != map[parent_row][parent_col])
            );
        }
        for (auto i = 0; i < 4; ++i) {
            const auto new_row = row + dir_1[i];
            const auto new_col = col + dir_2[i];
            if (
                new_row >= 0 && new_row < h && new_col >= 0 && new_col < w &&
                parents[new_row][new_col][0] == -1 && (new_row || new_col)
            ) {
                parents[new_row][new_col] = front;
                if (map[new_row][new_col] == map[row][col]) {
                    process.push_front(Location({new_row, new_col}));
                } else {
                    process.push_back(Location({new_row, new_col}));
                }
            }
        }
    }

    auto animals = 0;

    for (const auto& x : distances) {
        animals = max(*max_element(x.begin(), x.end()), animals);
    }

    cout << animals << '\n';

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

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