| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 484888 | ali22413836 | Tracks in the Snow (BOI13_tracks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
if(y == 0) return 1 ;
if(y == 1) return x ;
ll ret = mypower(x , y / 2);
ret = (ret * ret) % mod;
if(y % 2) ret = ( ret * x ) % mod ;
return ret ;
}
ll n , m ;
char a[2000][2000] ;
ll vis[2000][2000] ;
ll sta , sta2 , en , en2 ;
ll di[] = {0 , 0 , 1 , -1} , di2[] = {1 , -1 , 0 , 0} ;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m ;
for(int i = 0 ; i < n ; i++){
cin >> a[i] ;
}
deque < pair < ll , ll > > q ;
q.push_back({sta , sta2}) ;
sta = 0 , sta2 = 0 ;
vis[sta][sta2] = 1 ;
ll ans = 0 ;
while(!q.empty()){
pair < ll , ll > x ;
x = q.front() ;
q.pop_front() ;
ans = max(ans , vis[x.first][x.second]) ;
ll i = x.first , j = x.second ;
for(int k = 0 ; k < 4 ; k++){
ll ni = i + di[k] , nj = j + di2[k] ;
if(ni < n && ni >= 0 && nj < m && nj >= 0 && a[ni][nj] != '.'s && vis[ni][nj] == 0){
if(a[ni][nj] == a[i][j]){
q.push_front({ni , nj}) ;
vis[ni][nj] = vis[i][j] ;
}
else{
q.push_back({ni , nj}) ;
vis[ni][nj] = vis[i][j] + 1 ;
}
}
}
}
cout << ans << endl ;
return 0 ;
}