Submission #554484

#	Time	Username	Problem	Language	Result	Execution time	Memory
554484		savackexp	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1107 ms	345088 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define in insert
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be  begin()
#define en  end()
#define pb push_back
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;/*
ll  binpow(ll  a, ll  b) {
    ld  res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }

    return res;
}
unsigned long long power(unsigned long long x,
                                ll y, ll p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

unsigned long long modInverse(unsigned long long n,
                                            ll p)
{
    return power(n, p - 2, p);
}
*/
ll n , m ;
char grid[4005][4005];
ll vis[4006][4006];
ll level[4006][4006];
ll dx[]={0  , 0 , 1 , -1};
ll dy[]={-1  , 1 , 0 , 0};
bool valid(ll x , ll y)
{
    return x>=0 && y>=0 && x<n && y<m && grid[x][y] != '.' && !vis[x][y];
}
ll max1=0;
void bfs(ll x ,ll y)
{
    deque<pair<ll,ll>>q;
    q.push_front({x,y});
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            level[i][j]=-1e18;
        }
    }
    level[x][y]=0;
    vis[x][y]=1;
    while(!q.empty())
    {
        pair<ll,ll>p = q.front();
        q.pop_front();
        max1=max(max1 , level[p.fi][p.se]);
        for(int i=0;i<4;i++)
        {
            ll nx = p.fi + dx[i];
            ll ny = p.se + dy[i];
            if(!valid(nx , ny))continue;
            if(grid[nx][ny]==grid[p.fi][p.se])
            {
                level[nx][ny]=level[p.fi][p.se];
                q.push_front({nx,ny});
            }
            else
            {
                level[nx][ny]=level[p.fi][p.se]+1;
                q.push_back({nx,ny});
            }
            vis[nx][ny]=1;
        }
    }
}




int main()
{

        fastio

        //freopen("lasers.in","r",stdin);
        //freopen("lasers.out","w",stdout);

        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<s.size();j++)
            {
                grid[i][j]=s[j];
            }
        }

        bfs(0 , 0);

        cout<<max1+1<<endl;


































    return 0;
    }
/*
5 6
0 4 0
0 3 1
0 1 1
0 2 1
1 2 1
3 4 0

*/

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for(int j=0;j<s.size();j++)
      |                         ~^~~~~~~~~

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