// Problem Link: https://oj.uz/problem/view/BOI13_tracks
#include <bits/stdc++.h>
using namespace std;
#define solution_01BFS
#ifdef solution_DOUBT
#define UNTOUCHED '.'
constexpr int DIRNS(4);
constexpr pair<int, int> MOVE[DIRNS]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
vector<vector<char>> meadow; // NOTE: Don't use variable name map as there exists std::map in C++ STL
int count(int height, int width)
{
vector<vector<bool>> vis(height, vector<bool>(width));
int res = 0;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
{
char curr_animal = meadow[i][j];
if (!vis[i][j] && curr_animal != UNTOUCHED)
{
vector<vector<bool>> curr(height, vector<bool>(width));
res++;
stack<pair<int, int>> st; // h, w
st.emplace(i, j);
vis[i][j] = true;
curr[i][j] = true;
while (!st.empty())
{
auto [h, w] = st.top();
st.pop();
for (int d = 0; d < DIRNS; d++)
{
int new_h = h + MOVE[d].first, new_w = w + MOVE[d].second;
if (new_h >= 0 && new_h < height && new_w >= 0 && new_w < width && meadow[new_h][new_w] != UNTOUCHED)
if (!vis[new_h][new_w] && meadow[new_h][new_w] == curr_animal)
vis[new_h][new_w] = true, st.emplace(new_h, new_w), curr[new_h][new_w] = true;
else if (vis[new_h][new_w] && !curr[new_h][new_w]) // IMP: else ALWAYS MATHES NEAREST UNMATCHED if
st.emplace(new_h, new_w), curr[new_h][new_w] = true;
}
}
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H, W;
cin >> H >> W;
meadow.assign(H, vector<char>(W));
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
cin >> meadow[i][j];
cout << count(H, W) << '\n';
return 0;
}
#endif
#ifdef solution_01BFS
/*
In this question, every valid animal path starts at (1,1) and ends at (N,M)
So any path that reaches any cell (x,y) can be extended to (N,M).
answer= max of (min component switches on path P) over all paths P from (1, 1) to any other cell
now this max is from (1, 1) to (N, M) always
*/
constexpr char UNTOUCHED('.');
constexpr int DIRNS(4);
constexpr int MAX_SIZE(4000);
constexpr int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int n, m, ans = 1, depth[MAX_SIZE][MAX_SIZE]; // depth[i][j] = min no. of animals required to reach cell (i, j) from (0, 0) including (0, 0) and (i, j) = 1 + min. no of letter changes along any valid path from (0, 0) to (i, j)
string snow[MAX_SIZE]; // input to be taken over here
// Checks whether cell inside snow grid
inline bool inside(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != UNTOUCHED); }
int main()
{
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m; // n, m are globally declared where n is height and m is width
for (int i = 0; i < n; i++)
cin >> snow[i];
deque<pair<int, int>> q;
q.emplace_back(0, 0);
depth[0][0] = 1;
while (!q.empty())
{
auto [cx, cy] = q.front();
q.pop_front();
// Track maximum animals needed so far
ans = max(ans, depth[cx][cy]);
// Explore 4 neighboring cells
for (int d = 0; d < DIRNS; d++)
{
int nx = cx + dx[d], ny = cy + dy[d];
// If neighbor is valid and not yet visited (depth == 0 means univisted)
if (inside(nx, ny) && depth[nx][ny] == 0)
{
if (snow[nx][ny] == snow[cx][cy]) // Same animal
{
depth[nx][ny] = depth[cx][cy];
q.emplace_front(nx, ny);
}
else
{
depth[nx][ny] = depth[cx][cy] + 1;
q.emplace_back(nx, ny);
}
}
}
}
cout << ans << '\n';
}
#endif
