Submission #1256298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256298		ericl23302	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	522 ms	87644 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w, 0));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) cin >> grid[i][j];
    }

    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    vector<int> distances(h * w, -1);
    distances[0] = 1;
    deque<int> q;
    q.push_front(0);

    while (!q.empty()) {
        int cur = q.front();
        q.pop_front();

        for (auto &i : directions) {
            int newX = (cur / w) + i.first, newY = (cur % w) + i.second,
                newVal = newX * w + newY;
            if (newX < 0 || newX >= h || newY < 0 || newY >= w) continue;
            if (distances[newVal] != -1) continue;
            if (grid[newX][newY] == '.') continue;
            distances[newVal] =
                distances[cur] + (grid[newX][newY] != grid[cur / w][cur % w]);
            if ((grid[newX][newY] != grid[cur / w][cur % w]))
                q.push_back(newVal);
            else
                q.push_front(newVal);
        }
    }

    int res = 0;
    for (auto &i : distances) res = max(res, (int)i);

    cout << res << '\n';

    return 0;
}

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