Submission #1243662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243662		wedonttalkanymore	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	2102 ms	305604 KiB

tracks

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

int n, m;
vector <vector <char> > a;
vector <vector <int> > length;
struct item {
    int x, y, val;
    bool operator <(const item &other) const {
        return val > other.val;
    }
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dijk() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            length[i][j] = inf;
        }
    }
    length[1][1] = 1;
    priority_queue <item> q;
    q.push({1, 1, 1});
    while(q.size()) {
        auto [x, y, val] = q.top();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > n || nx < 1 || ny > m || ny < 1 || a[nx][ny] == '.') continue;
            if (a[x][y] == a[nx][ny] && length[nx][ny] > length[x][y]) {
                length[nx][ny] = length[x][y];
                q.push({nx, ny, length[nx][ny]});
            }
            if (a[x][y] != a[nx][ny] && length[nx][ny] > length[x][y] + 1) {
                length[nx][ny] = length[x][y] + 1;
                q.push({nx, ny, length[nx][ny]});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (length[i][j] < inf) ans = max(ans, length[i][j]);
        }
    }
    cout << ans + 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    a.assign(n + 1, vector <char> (m + 1, 0));
    length.assign(n + 1, vector <int> (m + 1, 0));
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j - 1];
        }
    }
    dijk();
    return 0;
}

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