Submission #877980

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

tracks

#include <bits/stdc++.h>

using namespace std;

int w, h, ans;
char snow[4001][4001];
int check[4001][4001];

void dfs(int x, int y, int br)
{
    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)check[x-1][y]=br+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)check[x+1][y]=br+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)check[x][y-1]=br+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)check[x][y+1]=br+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];
    }
    check[1][1]=1;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(snow[i][j]=='.')check[i][j]=-1;
            else {dfs(i, j, check[i][j]); ans=max(ans, check[i][j]);}
        }
    }
    cout<<ans;
    return 0;
}

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