#include <algorithm> #include <array> #include <cassert> #include <deque> #include <functional> #include <iostream> #include <cstring> #include <ctime> #include <chrono> #include <numeric> #include <queue> #include <set> #include <vector> #include <random> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; #define all(x) (x).begin(), (x).end() #define isz(x) (int)(x.size()) mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int sz = 4200, inf = 1000000000; const ll mod = 1000000007, INF = 1000000000000000000; char a[sz][sz]; int d[sz][sz]; int n, m; void djk() { priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq; pq.push({1, 1, 1}); d[1][1] = 1; while (!pq.empty()) { auto [dis, i, j] = pq.top(); pq.pop(); if (d[i][j] != dis) continue; if (j + 1 <= m && a[i][j+1] != '.' && d[i][j+1] > d[i][j] + (a[i][j] != a[i][j+1])) { d[i][j+1] = d[i][j] + (a[i][j] != a[i][j+1]); pq.push({d[i][j+1], i, j+1}); } if (j >= 2 && a[i][j-1] != '.' && d[i][j-1] > d[i][j] + (a[i][j] != a[i][j-1])) { d[i][j-1] = d[i][j] + (a[i][j] != a[i][j-1]); pq.push({d[i][j-1], i, j-1}); } if (i + 1 <= n && a[i+1][j] != '.' && d[i+1][j] > d[i][j] + (a[i][j] != a[i+1][j])) { d[i+1][j] = d[i][j] + (a[i][j] != a[i+1][j]); pq.push({d[i+1][j], i+1, j}); } if (i >= 2 && a[i-1][j] != '.' && d[i-1][j] > d[i][j] + (a[i][j] != a[i-1][j])) { d[i-1][j] = d[i][j] + (a[i][j] != a[i-1][j]); pq.push({d[i-1][j], i-1, j}); } } } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) { d[i][j] = inf; } } djk(); int mx = 0; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) { mx = max(mx, (d[i][j] != inf ? d[i][j] : -1)); } } cout << mx << '\n'; } void precompute() {} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL // freopen("err.log", "w", stderr); // freopen("in.txt", "r", stdin); #endif precompute(); solve(); }