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>
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |