Submission #535872

#	Time	Username	Problem	Language	Result	Execution time	Memory
535872		neennera	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	548 ms	122364 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second

int N,M,ans=0;
int depth[4005][4005];
string snow[4000];
int wx[5]={-1,0,0,1}, wy[5]={0,-1,1,0};

int check(int i,int j){
    return (i>=0&&i<N&&j>=0&&j<M&&snow[i][j]!='.');
}

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

    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> snow[i];

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            depth[i][j]=0;
    }

    deque<pair<int,int>> q;
    q.push_back({0,0});
    depth[0][0]=1;

    while(!q.empty()){
        int x=q.front().ft;
        int y=q.front().sd;
        q.pop_front();
        ans=max(ans,depth[x][y]);
        //cout << x << " " << y << endl;
        for(int i=0;i<4;i++){
            int nx=x+wx[i];
            int ny=y+wy[i];
            //cout << i << " : " << nx << " " << ny << endl;
            //if(snow[nx][ny]=='.'){continue;}
            if(check(nx,ny)&&depth[nx][ny]==0){
                if(snow[x][y]==snow[nx][ny]){
                    depth[nx][ny]=depth[x][y];
                    q.push_front(make_pair(nx,ny));
                }else{
                    depth[nx][ny]=depth[x][y]+1;
                    q.push_back(make_pair(nx,ny));
                }
            }
        }
    }

    cout << ans;
}

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