Submission #885039

#	Time	Username	Problem	Language	Result	Execution time	Memory
885039		tigar	Tracks in the Snow (BOI13_tracks)	C++14	97.81 / 100	1596 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int w, h, ans;
char snow[4001][4001];
int check[4001][4001];
queue<pair< pair<int, int>, int> >ord;
int brr=1;

void dfs(int x, int y, int br)
{
    //cout<<br<<"\n";
    if(x-1>0)
    {
        if(snow[x-1][y]==snow[x][y] and check[x-1][y]==0){check[x-1][y]=br; dfs(x-1, y, br);}
        else if(snow[x-1][y]!='.')
        {
            if(check[x-1][y]==0){ord.push({{x-1, y}, br+1});}
        }
        else if(snow[x-1][y]=='.')check[x-1][y]=-1;
    }
    if(x+1<=h)
    {
        if(snow[x][y]==snow[x+1][y] and check[x+1][y]==0){check[x+1][y]=br; dfs(x+1, y, br);}
        else if(snow[x+1][y]!='.')
        {
            if(check[x+1][y]==0){ord.push({{x+1, y}, br+1});}
        }
        else if(snow[x+1][y]=='.')check[x+1][y]=-1;
    }
    if(y-1>0)
    {
        if(snow[x][y]==snow[x][y-1] and check[x][y-1]==0){check[x][y-1]=br; dfs(x, y-1, br);}
        else if(snow[x][y-1]!='.')
        {
            if(check[x][y-1]==0){ord.push({{x, y-1}, br+1});}
        }
        else if(snow[x][y-1]=='.')check[x][y-1]=-1;
    }
    if(y+1<=w)
    {
        if(snow[x][y]==snow[x][y+1] and check[x][y+1]==0){check[x][y+1]=br; dfs(x, y+1, br);}
        else if(snow[x][y+1]!='.')
        {
            if(check[x][y+1]==0){ord.push({{x, y+1}, br+1});}
        }
        else if(snow[x][y+1]=='.')check[x][y+1]=-1;
    }
    return;
}

int main()
{
    cin>>h>>w;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)cin>>snow[i][j];
    }
    ord.push({{1, 1}, 1});
    while(!ord.empty())
    {
        int xx=ord.front().first.first, yy=ord.front().first.second, bb=ord.front().second;
        ord.pop();
        if(!check[xx][yy])
        {
            check[xx][yy]=bb;
            dfs(xx, yy, bb);
            ans=max(ans, bb);
        }
    }
    //for(int i=1; i<=h; i++){for(int j=1; j<=w; j++)cout<<check[i][j]; cout<<endl;}
    cout<<ans;
    return 0;
}

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