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 pb push_back
#define ll long long
#define mid (l+r)/2
#define left 2*i+1
#define righ 2*i+2
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n,m,cnt;
char c[1010][1010];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int com[1010][1010];
bool check(int x,int y){
if(x<1||x>n||y<1||y>m)return 1;
return 0;
}
void ass(int x,int y){
com[x][y]=cnt;
for(int i=0;i<4;i++){
int tox=x+dx[i],toy=y+dy[i];
if(check(tox,toy))continue;
if(com[tox][toy])continue;
if(c[tox][toy]!=c[x][y])continue;
ass(tox,toy);
}
}
vector<int>v[1000006];
map<pair<int,int>,bool>don;
int dfs(int nod,int par,int dep){
int mx=dep;
for(auto x:v[nod]){
if(x==par)continue;
mx=max(mx,dfs(x,nod,dep+1));
}
return mx;
}
int main()
{
FAST
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(c[i][j]=='*')continue;
if(!com[i][j]){
cnt++;
ass(i,j);
}
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<com[i][j];
}
cout<<endl;
}*/
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
if(!com[x][y])continue;
for(int k=0;k<4;k++){
int tox=x+dx[k],toy=y+dy[k];
if(check(tox,toy))continue;
if(com[x][y]==com[tox][toy])continue;
if(!com[tox][toy])continue;
int a=com[x][y],b=com[tox][toy];
if(don[{a,b}])continue;
v[a].pb(b);
v[b].pb(a);
don[{a,b}]=1;
don[{b,a}]=1;
}
}
}
/*for(int i=1;i<cnt;i++){
cout<<i<<" ====> ";
for(auto x:v[i])cout<<x<<' ';cout<<endl;
}*/
cout<<dfs(1,0,1)<<endl;;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |