#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "zoo"
using namespace std;
/**Debugging Tool **/
void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*----------------------------------*/
/** Vector nhieu chieu **/
template<int D, typename T>
struct Vec: public vector<Vec<D - 1, T>>{
static_assert(D >= 1, "vector dimensions must be greater than 0");
template<typename... Args>
Vec(int n = 0, Args... args): vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)){
}
};
template<typename T>
struct Vec<1, T>: public vector<T> {
Vec(int n = 0, const T& val = T()): vector<T>(n, val) {};
};
/*--------------------------------*/
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1009 + 9;
int n, m;
char str[MAXN][MAXN];
int idComponent[MAXN][MAXN], componentCount = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<ii> q;
vector<vector<int>> g;
map<ii, bool> mp;
bool valid(int x, int y){
return x >= 1 and x <= n and y >= 1 and y <= m and str[x][y] != '*';
}
void bfs(int x, int y){
idComponent[x][y] = ++componentCount;
q.push(ii(x, y));
while(!q.empty()){
int x1 = q.front().fi;
int y1 = q.front().se;
q.pop();
for(int d = 0; d < 4; d++){
int nx = x1 + dx[d];
int ny = y1 + dy[d];
if (!idComponent[nx][ny] and valid(nx, ny) and str[nx][ny] == str[x1][y1]){
idComponent[nx][ny] = componentCount;
q.push(ii(nx, ny));
}
}
}
}
ii best = ii(0, 0);
int dist[MAXN * MAXN];
void dfs(int u, int p, int d){
queue<int> q;
q.push(1);
memset(dist, 0x3f, sizeof(dist));
dist[1] = 1;
int ans = 0;
while(!q.empty()){
int u = q.front();
maximize(ans, dist[u]);
q.pop();
for(auto v: g[u]){
if (minimize(dist[v], dist[u] + 1)){
q.push(v);
}
}
}
cout << ans << endl;
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> str[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (idComponent[i][j] == 0 and str[i][j] != '*'){
bfs(i, j);
}
}
}
g.resize(componentCount + 1);
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// printf("%lld ", idComponent[i][j]);
// }
// printf("\n");
// }
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (i < n and str[i][j] != '*' and str[i + 1][j] != '*' and str[i + 1][j] != str[i][j]) {
// printf("%lld %lld %lld\n", i, j, idComponent[i][j]);
if (mp.find(ii(idComponent[i][j], idComponent[i + 1][j])) == mp.end()){
g[idComponent[i][j]].pb(idComponent[i + 1][j]);
g[idComponent[i + 1][j]].pb(idComponent[i][j]);
// printf("%lld %lld %lld %lld\n", i, j, i + 1, j);
// printf("%lld %lld\n", idComponent[i][j], idComponent[i + 1][j]);
mp[ii(idComponent[i][j], idComponent[i + 1][j])] = true;
mp[ii(idComponent[i + 1][j], idComponent[i][j])] = true;
}
}
if (j < m and str[i][j] != '*' and str[i][j + 1] != '*' and str[i][j] != str[i][j + 1]) {
if (mp.find(ii(idComponent[i][j], idComponent[i][j + 1])) == mp.end()){
// printf("%lld %lld %lld %lld\n", i, j, i, j + 1);
g[idComponent[i][j]].pb(idComponent[i][j + 1]);
g[idComponent[i][j + 1]].pb(idComponent[i][j]);
mp[ii(idComponent[i][j], idComponent[i][j + 1])] = true;
// printf("%lld %lld\n",idComponent[i][j], idComponent[i][j + 1]);
mp[ii(idComponent[i][j + 1], idComponent[i][j])] = true;
}
}
}
}
////
dfs(idComponent[n][m], -1, 0);
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
