Submission #754137

#	Time	Username	Problem	Language	Result	Execution time	Memory
754137		ivaziva	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1422 ms	252240 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define MAXN 4010

long long n;
long long m;
char matrica[MAXN][MAXN];
long long dist[MAXN][MAXN];
deque<pair<long long,long long>> bfsq;
long long sx[5];
long long sy[5];
long long ans;

bool unutar(long long a,long long b)
{
    if (a>=1 and a<=n and b>=1 and b<=m and matrica[a][b]!='.') return true;
    else return false;
}

void bfs(long long x,long long y)
{
    for (long long i=0;i<MAXN;i++)
    {
        for (long long j=0;j<MAXN;j++) dist[i][j]=LLONG_MAX;
    }
    dist[x][y]=0;
    bfsq.push_front({x,y});
    ans=0;
    while (bfsq.empty()==false)
    {
        long long nodex=bfsq.front().first;
        long long nodey=bfsq.front().second;
        bfsq.pop_front();
        ans=max(ans,dist[nodex][nodey]);
        for (long long i=1;i<=4;i++)
        {
            long long sledx=nodex+sx[i];
            long long sledy=nodey+sy[i];
            if (unutar(sledx,sledy) and dist[sledx][sledy]==LLONG_MAX)
            {
                if (matrica[nodex][nodey]==matrica[sledx][sledy])
                {
                    dist[sledx][sledy]=dist[nodex][nodey];
                    bfsq.push_front({sledx,sledy});
                }
                else
                {
                    dist[sledx][sledy]=dist[nodex][nodey]+1;
                    bfsq.push_back({sledx,sledy});
                }
            }
        }
    }
}

int main()
{
    sx[1]=1,sy[1]=0;
    sx[2]=-1,sy[2]=0;
    sx[3]=0,sy[3]=1;
    sx[4]=0,sy[4]=-1;
    cin>>n>>m;
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++) cin>>matrica[i][j];
    }
    bfs(1,0);
    cout<<ans<<endl;
}

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