#include <iostream> #include <vector> #include <queue> using namespace std; struct heap { int i, j, w; bool operator < (const heap &o) const { return w > o.w; } }; vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<string> grid(n); for (auto &s:grid) cin >> s; auto invalid = [&](int i, int j) -> bool { return i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '.'; }; priority_queue<heap> pq; vector<vector<int>> dist(n, vector<int>(m, 0)); vector<vector<bool>> vis(n, vector<bool>(m, false)); dist[0][0] = 1; vis[0][0] = true; pq.push({0, 0, 1}); int ans = 0; while (!pq.empty()){ auto [i, j, W] = pq.top(); pq.pop(); ans = max(ans, dist[i][j]); for (auto [di, dj]:dir){ if (invalid(i + di, j + dj) || vis[i + di][j + dj]) continue; if (grid[i + di][j + dj] != grid[i][j]){ dist[i + di][j + dj] = dist[i][j] + 1; vis[i + di][j + dj] = true; pq.push({i + di, j + dj, dist[i][j] + 1}); } else { dist[i + di][j + dj] = dist[i][j]; vis[i + di][j + dj] = true; pq.push({i + di, j + dj, dist[i][j]}); } } } // for (int i = 0;i < n;i++){ // for (int j = 0;j < m;j++) // cout << dist[i][j] << ' '; // cout << '\n'; // } cout << ans << '\n'; }