Submission #1211139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211139		islam_2010	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	423 ms	124020 KiB

tracks

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int sz = 4005;
int n, m;
string a[sz];
int d[sz][sz]; 

int dx[] = {0, -1, 1, 0};
int dy[] = {1, 0, 0, -1};

bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '.';
}

int bfs() {
    for (int i = 0; i < n; ++i)
        fill(d[i], d[i] + m, -1); 

    deque<pii> q;
    d[0][0] = 1; 
    q.push_front({0, 0});

    int res = 1;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop_front();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!check(nx, ny)) continue;

            if (d[nx][ny] == -1) {
                if (a[nx][ny] == a[x][y]) {
                    d[nx][ny] = d[x][y];
                    q.push_front({nx, ny});
                } else {
                    d[nx][ny] = d[x][y] + 1;
                    q.push_back({nx, ny});
                }
                res = max(res, d[nx][ny]);
            }
        }
    }

    return res;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    cout << bfs() << '\n';
    return 0;
}

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