Submission #940165

#	Time	Username	Problem	Language	Result	Execution time	Memory
940165		VKnight	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	885 ms	372268 KiB

tracks

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define gett(tup,ind) get<ind>(tup)
#define print(x) for (auto i:x){cout<<i<<" ";}cout<<endl;

using namespace std;

void solve(){
    int h,w;cin>>h>>w;

    vector <string> arr(h);
    for (int i=0;i<h;i++){
        cin>>arr[i];
    }

    vector <vector<int>> dis(h,vector <int> (w,-1));
    deque <tuple<int,int,int>> dq;dq.emplace_back(0,0,1);
    while (dq.size()){
        auto [a,b,c]=dq.front();dq.pop_front();
        if (dis[a][b]!=-1)continue;
        dis[a][b]=c;
        if (a+1<h && arr[a+1][b]!='.'){if (arr[a][b]==arr[a+1][b]){dq.emplace_front(a+1,b,c);}else{dq.emplace_back(a+1,b,c+1);}}
        if (b+1<w && arr[a][b+1]!='.'){if (arr[a][b]==arr[a][b+1]){dq.emplace_front(a,b+1,c);}else{dq.emplace_back(a,b+1,c+1);}}
        if (a>0 && arr[a-1][b]!='.'){if (arr[a][b]==arr[a-1][b]){dq.emplace_front(a-1,b,c);}else{dq.emplace_back(a-1,b,c+1);}}
        if (b>0 && arr[a][b-1]!='.'){if (arr[a][b]==arr[a][b-1]){dq.emplace_front(a,b-1,c);}else{dq.emplace_back(a,b-1,c+1);}}
    }

    int ans=0;
    for (auto i:dis){
        ans=max(ans,*max_element(all(i)));
    }

    cout<<ans<<endl;

    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    int no_test=1;
    //cin>>no_test;
    while (no_test--){solve();}
    return 0;
}

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