Submission #1153542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153542		kiwimsy	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1421 ms	613244 KiB

tracks

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

ll n, m, ans = 0;
vector<string> g;
vector<vector<ll>> dist; 
vector<vector<bool>> vis;

void bfs(ll y, ll x){
    deque<pair<ll, ll>> q;
    q.push_back({y, x});
    dist[y][x] = 1;
    while(!q.empty()){
        pair<ll, ll> val = q.front();
        ll vy = val.first, vx = val.second;
        q.pop_front();
        if(vis[vy][vx]) continue;
        for(ll dy = (vy > 0 ? -1 : 0); dy <= (vy < n-1 ? 1 : 0); dy++){
            if(g[vy+dy][vx] != '.' && vis[vy+dy][vx] == false){
                if(g[vy][vx] == g[vy+dy][vx]){
                    q.push_front({vy+dy, vx});
                    dist[vy+dy][vx] = dist[vy][vx];
                }
                else{
                    q.push_back({vy+dy, vx});
                    dist[vy+dy][vx] = dist[vy][vx] + 1;
                }
            }
        }
        for(ll dx = (vx > 0 ? -1 : 0); dx <= (vx < m-1 ? 1 : 0); dx++){
            if(g[vy][vx+dx] != '.' && vis[vy][vx+dx] == false){
                if(g[vy][vx] == g[vy][vx+dx]){
                    q.push_front({vy, vx+dx});
                    dist[vy][vx+dx] = dist[vy][vx];
                }
                else{
                    q.push_back({vy, vx+dx});
                    dist[vy][vx+dx] = dist[vy][vx] + 1;
                }
            }
        }
        vis[vy][vx] = true;
        ans = dist[vy][vx];
    }
}

int main(){
    cin >> n >> m;
    g.resize(n), dist.resize(n), vis.resize(n);
    for(ll i = 0; i < n; i++){
        cin >> g[i];
        dist[i].assign(m, -1);
        vis[i].assign(m, false);
    }
    bfs(0, 0);
    cout << ans << "\n";
}

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