#include <bits/stdc++.h> using namespace std; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; void solve() { int H, W; cin >> H >> W; vector grid(H + 1, vector(W + 1, '.')); for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cin >> grid[i][j]; } } priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq; vector dist(H + 1, vector(W + 1, (int)1E9)); vector vis(H + 1, vector(W + 1, false)); int ans = 1; dist[1][1] = 1; pq.push({1, {1,1}}); while (!pq.empty()) { auto [a, b] = pq.top(); pq.pop(); auto [y, x] = b; if (vis[y][x]) continue; vis[y][x] = true; ans = max(ans, a); for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 1 || ny > H || nx < 1 || nx > W || grid[ny][nx] == '.') continue; if (dist[y][x] + (grid[y][x] != grid[ny][nx]) < dist[ny][nx]) { dist[ny][nx] = dist[y][x] + (grid[y][x] != grid[ny][nx]); pq.push({dist[ny][nx], {ny, nx}}); } } } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }