Submission #1179581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179581		PakinDioxide	Tracks in the Snow (BOI13_tracks)	C++17	65.42 / 100	2098 ms	105628 KiB

tracks

/*
    author  : PakinDioxide
    created : 06/04/2025 16:36
    task    : BOI13_tracks
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    string a[n];
    for (auto &e : a) cin >> e;
    int dis[n][n];
    for (auto &E : dis) for (auto &e : E) e = INT_MAX;
    dis[0][0] = 1;
    priority_queue <tuple <int, int, int>> q;
    q.emplace(-1, 0, 0);
    int ans = 0;
    while (!q.empty()) {
        auto [w, x, y] = q.top();
        q.pop();
        w=-w;
        if (dis[x][y] != w) continue;
        ans = max(ans, w);
        for (auto [dx, dy] : d) {
            int nx = x+dx, ny = y+dy;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == '.') continue;
            if (dis[nx][ny] > dis[x][y] + (a[x][y] != a[nx][ny])) q.emplace(-(dis[nx][ny] = dis[x][y] + (a[x][y] != a[nx][ny])), nx, ny);
        }
    }
    cout << ans << '\n';
}

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