Submission #648117

#	Time	Username	Problem	Language	Result	Execution time	Memory
648117		borisAngelov	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	786 ms	131060 KiB

tracks

#include <iostream>
#include <utility>
#include <deque>
#include <tuple>

using namespace std;

const int MAXN = 4005;

int n, m;
char table[MAXN][MAXN];

int levels[MAXN][MAXN];

pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> table[i][j];
        }
    }

    deque<pair<int, int>> q; q.push_back({1, 1});
    levels[1][1] = 1;

    int ans = 1;

    while (!q.empty()) {
        int x, y; tie(x, y) = q.front();
        q.pop_front();

        ans = max(ans, levels[x][y]);

        for (int d = 0; d < 4; d++) {
            int x2 = x + dirs[d].first;
            int y2 = y + dirs[d].second;

            if (x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue;
            if (levels[x2][y2] != 0) continue;
            if (table[x2][y2] == '.') continue;

            if (table[x2][y2] == table[x][y]) {
                q.push_front({x2, y2});
                levels[x2][y2] = levels[x][y];
            } else {
                q.push_back({x2, y2});
                levels[x2][y2] = 1 + levels[x][y];
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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