Submission #844882

#	Time	Username	Problem	Language	Result	Execution time	Memory
844882		elotelo966	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	470 ms	236872 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1e11
#define mod 100000000
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
char dizi[4005][4005];
int cev=0,x[4]={1,-1,0,0},y[4]={0,0,1,-1},dep[4005][4005],n,m;

inline int bfs(){
    deque <pair<int,int>> de;
    de.push_back({0,0});
    dep[0][0]=1;
    while(de.size()){
        int x1=de.front().first;
        int y1=de.front().second;

        de.pop_front();
        cev=max(cev,dep[x1][y1]);
        for(int i=0;i<4;i++){
            int yx=x1+x[i],yy=y1+y[i];
            if(yx<0 || yx>=n || yy<0 || yy>=m)continue;
            if(dizi[yx][yy]=='.')continue;
            if(dep[yx][yy]!=0)continue;
            if(dizi[yx][yy]==dizi[x1][y1]){
                dep[yx][yy]=dep[x1][y1];
                de.push_front({yx,yy});
            }else{
                dep[yx][yy]=dep[x1][y1]+1;
                de.push_back({yx,yy});
            }
        }
    }
    return cev;
}

int32_t main(){
    faster
    cin>>n>>m;
    string deg;
    for(int i=0;i<n;i++){
        cin>>deg;
        for(int j=0;j<m;j++){
            dizi[i][j]=deg[j];
        }
    }
    cout<<bfs()<<'\n';
    return 0;
}

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