#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() { deque<array<int, 2>> pq; pq.push_front({1, 1}); d[1][1] = 1; while (!pq.empty()) { auto [i, j] = pq.front(); pq.pop_front(); 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]); if (a[i][j] == a[i][j+1]) pq.push_front({i, j+1}); else pq.push_back({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]); if (a[i][j] == a[i][j-1]) pq.push_front({i, j-1}); else pq.push_back({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]); if (a[i][j] == a[i+1][j]) pq.push_front({i+1, j}); else pq.push_back({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]); if (a[i][j] == a[i-1][j]) pq.push_front({i-1, j}); else pq.push_back({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(); }