#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int h,w;
cin>>h>>w;
vector<string> g(h);
for(int i=0;i<h;i++) cin>>g[i];
int n=h*w;
const int INF=1e9;
vector<int> dist(n,INF);
deque<int> dq;
dist[0]=0;
dq.push_front(0);
int dr[4]={-1,1,0,0}, dc[4]={0,0,-1,1};
while(!dq.empty()){
int id=dq.front(); dq.pop_front();
int d=dist[id];
int r=id/w, c=id%w;
for(int k=0;k<4;k++){
int nr=r+dr[k], nc=c+dc[k];
if(nr<0||nr>=h||nc<0||nc>=w) continue;
if(g[nr][nc]=='.') continue;
int nid=nr*w+nc;
int w1 = g[nr][nc]!=g[r][c];
if(dist[nid]>d+w1){
dist[nid]=d+w1;
if(w1==0) dq.push_front(nid);
else dq.push_back(nid);
}
}
}
int mx=0;
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
if(g[i][j]!='.')
mx=max(mx,dist[i*w+j]);
cout<<mx+1;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |