Submission #553906

#TimeUsernameProblemLanguageResultExecution timeMemory
553906roctes7Tracks in the Snow (BOI13_tracks)C++17
100 / 100
1394 ms629440 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...