Submission #448685

#	Time	Username	Problem	Language	Result	Execution time	Memory
448685		Christopher_	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	643 ms	131124 KiB

tracks

#include <bits/stdc++.h>

using namespace std;


int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

        int n, m;
        cin >> n >> m;
        vector<string> mat(n);
        vector<vector<int>> dist(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
                cin >> mat[i];
        }

        deque<pair<int,int>> q;
        q.push_front({0, 0});
        dist[0][0] = 1;

        auto Check = [&](int x, int y) {
                return x >= 0 && x < n && y >= 0 && y < m && mat[x][y] != '.' && dist[x][y] == 0;
        };

        int ans = 0;
        while (!q.empty()) {
                int x = q.front().first, y = q.front().second; q.pop_front();
                ans = max(ans, dist[x][y]);
                for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (Check(nx, ny)) {
                                if (mat[nx][ny] == mat[x][y]) {
                                        dist[nx][ny] = dist[x][y];
                                        q.push_front({nx, ny});
                                } else {
                                        dist[nx][ny] = dist[x][y] + 1;
                                        q.push_back({nx, ny});
                                }
                        }
                }
        }
        cout << ans << '\n';
}

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