Submission #1198820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198820		Francisco_Martin	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	864 ms	405228 KiB

tracks

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

#define debug(v) cerr<<#v" = "<<(v)<<"\n";
#define debugvec(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<v[i]<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define debugvecp(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<"[ "<<v[i].fst<<" "<<v[i].snd<<" ]"<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define fst first
#define snd second
#define gcd(x,y) __gcd(x,y)
#define OnlineJudge(s) freopen((s".in"),"r",stdin); freopen((s".out"),"w",stdout);
#define fastIO() cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);
#define boolsolve() cout<<(solve()?"Yes":"No");

using ll=long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;

const ll INF=1e12;
const ll MOD=1e9+7;
const ll MAXN=1e6+1;

ll dx[]={1,-1,0,0}, dy[]={0,0,1,-1};

void solve(){
    ll h, w, ans=1; string s; deque<array<ll,3>> dq;
    cin >> h >> w;
    vvll B(h,vll(w,0)); vector<vector<char>> A(h,vector<char>(w));
    for(int i=0; i<h; i++){
        cin >> s;
        for(int j=0; j<w; j++) A[i][j]=s[j];
    }
    dq.push_front({0,0,1});
    while(!dq.empty()){
        auto[x,y,v]=dq.front(); dq.pop_front();
        if(x<0 || x>=h || y<0 || y>=w || A[x][y]=='.' || B[x][y]) continue;
        ans=max(ans,v); B[x][y]=v;
        for(int i=0; i<4; i++){
            ll nx=x+dx[i], ny=y+dy[i];
            if(nx<0 || nx>=h || ny<0 || ny>=w || A[nx][ny]=='.' || B[nx][ny]) continue;
            if(A[x][y]!=A[nx][ny]) dq.push_back({nx,ny,v+1});
            else dq.push_front({nx,ny,v});
        }
    }
    cout << ans;
}

int main(){
    fastIO();
    //OnlineJudge("")
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
        //cout << "\n";
    }
    return 0;
}

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