//JAI BAJRANG BALI
#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;
#ifndef ONLINE_JUDGE
#include "./debugging.hpp" // pathname
#else
#define debug(...)
#endif
#define ndl "\n"
typedef long long int ll;
typedef unsigned long long int ull;
//#define int long long
// ... Rest of your template code ...
#define out1(x) cout<<x<<"\n";
#define out(x) cout<<x<<" ";
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(), greater<ll>())
#define yes() std::cout << "YES\n";
#define no() std::cout << "NO\n";
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define p 998244353
using ll = long long;
vll dx={1,-1,0,0};
vll dy={0,0,-1,1};
// 1,0 -1,0 0,-1 0,1
void solve(ll tc){
ll n,m; cin>>n>>m; vector<string> steps(n);
vector<vll> d(n,vll(m,0));
for(ll i=0;i<n;i++){
cin>>steps[i];
}
d[0][0]=1;
ll ans=1;
deque<vll> q;
q.push_front({0,0});
while(!q.empty()){
vll v1=q.front(); q.pop_front();
ll x1=v1[0]; ll y1=v1[1];
ans=max(ans,d[x1][y1]);
for(ll i=0;i<4;i++){
ll new_x=x1+dx[i];
ll new_y=y1+dy[i];
if(new_x>=0 and new_y>=0 and new_x<n and new_y<n and (steps[new_x][new_y]!='.')){
ll weight=0;
if(steps[new_x][new_y]!=steps[x1][y1]) {
weight++;
}
if(d[new_x][new_y]==0){
d[new_x][new_y]=d[x1][y1]+weight;
if(weight==0){
q.push_front({new_x,new_y});
}
else{
q.push_back({new_x,new_y});
}
}
}
}
}
out1(ans);
}
signed main(){
ll T=1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cin>>T;
for (ll tc = 1; tc <=T; tc++) solve(tc);
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
Compilation message
tracks.cpp:8:10: fatal error: ./debugging.hpp: No such file or directory
8 | #include "./debugging.hpp" // pathname
| ^~~~~~~~~~~~~~~~~
compilation terminated.
