Submission #1313654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313654		shirokito	Tracks in the Snow (BOI13_tracks)	C++20	78.13 / 100	2098 ms	79816 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ForUp(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define ForDn(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

using ll = long long;

const int N = 4000 + 24, INF = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int n, m; char a[N][N];
int f[N][N];

bool inside(int i, int j) {
    return (i >= 1 && i <= n && j >= 1 && j <= m);
}

void solve() {
    cin >> n >> m;

    ForUp (i, 1, n) ForUp (j, 1, m) {
        cin >> a[i][j];
    }

    ForUp (i, 1, n) ForUp (j, 1, m) {
        f[i][j] = INF;
    }

    f[1][1] = 1;

    queue<pair<int, int>> bfs; 
    bfs.push({1, 1});

    while (bfs.size()) {
        auto [u, v] = bfs.front();
        bfs.pop();

        ForUp (dir, 0, 3) {
            int i = u + dx[dir], j = v + dy[dir];

            if (!inside(i, j) || a[i][j] == '.') continue;

            if (f[u][v] + (a[u][v] != a[i][j]) < f[i][j]) {
                f[i][j] = f[u][v] + (a[u][v] != a[i][j]);
                bfs.push({i, j});
            }
        }
    }

    int res = 0;

    ForUp (i, 1, n) ForUp (j, 1, m) {
        if (a[i][j] != '.') res = max(res, f[i][j]);
    }

    cout << res << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

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