Submission #1295244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295244		al95ireyiz	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	994 ms	227696 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 5000 + 5;
 
ll n, m, k = 0;

char a[maxn][maxn];
ll dis[maxn][maxn];
void _() {
    cin >> n >> m;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <= m; j ++){
            cin >> a[i][j];
            dis[i][j] = INF;
        }
    }
    deque<pair<ll, ll>>d;
    d.push_back({1, 1});
    dis[1][1] = 1;
    while(!d.empty()){
        auto [x, y] = d.front();
        d.pop_front();
        for(auto [i, j] : vector<pair<ll, ll>>{{x - 1, y}, {x, y - 1}, {x + 1, y}, {x, y + 1}}){
            if(i <= 0 or j <= 0 or i > n or j > m) continue;
            if(a[i][j] == '.') continue;
            if(dis[i][j] > dis[x][y] + (a[x][y] != a[i][j])){
                dis[i][j] = dis[x][y] + (a[x][y] != a[i][j]);
                if(a[x][y] != a[i][j]) d.push_back({i, j});
                else d.push_front({i, j});
            }
        }
    }
    ll cv = 0;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <= m; j ++){
            if(dis[i][j] == INF) continue;
            cv = max(cv, dis[i][j]);
        }
    }
    cout << cv << '\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    // cin >> t;
    while(t --) _();
}

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