Submission #1076384

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

tracks

#include <bits/stdc++.h>

using namespace std;

#define MAXN 4001

int h,w;
int a[MAXN][MAXN];
int dist[MAXN][MAXN];
deque<pair<int,int>> bfsq;
pair<int,int> dir[4];
int ans=0;

bool check(int nodex,int nodey)
{
    if (nodex>=1 and nodex<=h and nodey>=1 and nodey<=w and a[nodex][nodey]!='.' and dist[nodex][nodey]==INT_MAX) return true;
    return false;
}

void bfs()
{
    for (int i=1;i<=h;i++)
    {
        for (int j=1;j<=w;j++) dist[i][j]=INT_MAX;
    }
    dist[1][1]=0;bfsq.push_front({1,1});
    while (bfsq.empty()==false)
    {
        int nodex=bfsq.front().first,nodey=bfsq.front().second;bfsq.pop_front();
        ans=max(ans,dist[nodex][nodey]);
        for (int i=0;i<4;i++)
        {
            int sledx=nodex+dir[i].first,sledy=nodey+dir[i].second;
            if (!check(sledx,sledy)) continue;
            if (a[sledx][sledy]==a[nodex][nodey]) {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()
{
    dir[0]={0,1},dir[1]={1,0},dir[2]={0,-1},dir[3]={-1,0};
    cin>>h>>w;
    for (int i=1;i<=h;i++)
    {
        string s;cin>>s;
        for (int j=1;j<=w;j++) a[i][j]=s[j-1];
    }
    bfs();
    cout<<ans+1<<endl;
}

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