Submission #1243130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243130		PokemonMaster	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1040 ms	331920 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define int long long
int X[]={-1,1,0,0};
int Y[]={0,0,-1,1};
int used[4001][4001],dist[4001][4001];
signed main()
{
    int n,m,emix=0;
    cin>>n>>m;
    char a[n+1][m+1];
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];};};
    deque <pair <int,int> > dq;
    dq.push_back({1,1});
    used[1][1]=1;
    while(!dq.empty())
    {
        int x=dq.front().first;
        int y=dq.front().second;
        dq.pop_front();
        for(int i=0;i<4;i++)
        {
            int to_x=X[i]+x;
            int to_y=Y[i]+y;
            if(!to_x || !to_y || to_x>n || to_y>m || used[to_x][to_y] || !(a[to_x][to_y]-'.'))continue;
            if(a[to_x][to_y]-a[x][y])
            {
                dq.push_back({to_x,to_y});
                used[to_x][to_y]=1;
                dist[to_x][to_y]=dist[x][y]+1;
                emix=max(emix,dist[x][y]+1);
            }else
            {
                dq.push_front({to_x,to_y});
                used[to_x][to_y]=1;
                dist[to_x][to_y]=dist[x][y];
                emix=max(emix,dist[x][y]);
            }
        }
    }
    cout<<emix+1;
}
//MBOI Mirbek Bakirov's Olympiad in Informatics :)

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