Submission #553906

#	Time	Username	Problem	Language	Result	Execution time	Memory
553906		roctes7	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1394 ms	629440 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
#define mpa make_pair
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;
}



bool vist[4002][4002];
int dist [4002][4002];
string arr [4002][4002];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};



int main()
{

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


ll n,m;
cin>>n>>m;

for (int i=1;i<=n;i++){
    string s ;cin>>s;
    for (int j=1;j<=m;j++){
        arr[i][j]=s[j-1];
    }
}

int ans=0;

deque<pair<int,int>> q;
q.push_front(mpa(1,1));
vist[1][1]=true;

while (!q.empty()){
    int x=q.front().fi;
    int y =q.front().se;
    q.pop_front();

    ans=max(ans,dist[x][y]);

    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];

        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vist[nx][ny]&&arr[nx][ny]!="."){
            vist[nx][ny]=true;
            if(arr[nx][ny]==arr[x][y]){
                q.push_front(mpa(nx,ny));
                dist[nx][ny]=dist[x][y];
            }else {
              q.push_back(mpa(nx,ny));
                dist[nx][ny]=dist[x][y]+1;
            }

        }
    }
}

cout<<ans+1;
return 0;


}








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);
}

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