#include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<unordered_map> #include<unordered_set> using namespace std; using ll = long long; ll mod = 1e9 + 7; ll gcd(ll a, ll b) { if (b == 0)return a; else return gcd(b, a % b); } void solve() { int n, m; cin >> n >> m; vector<string>v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } if (v[0][0] == '.') { cout << 0 << endl; return; } int mx = 0; priority_queue<pair<int, pair<int, int>>>q; vector<vector<int>>dist(n, vector<int>(m, 1e9)); q.push({ -1,{0,0} }); dist[0][0] = 1; while (q.size()) { int i = q.top().second.first, j = q.top().second.second, qash = -q.top().first; q.pop(); if (qash != dist[i][j])continue; mx = max(mx, qash); if (i + 1 < n) { if (v[i + 1][j] != '.') { if (v[i + 1][j] == v[i][j]) { if (qash < dist[i + 1][j]) { dist[i + 1][j] = qash; q.push({ -qash,{i + 1,j} }); } } else { qash++; if (qash < dist[i + 1][j]) { dist[i + 1][j] = qash; q.push({ -qash,{i + 1,j} }); } qash--; } } } if (j + 1 < m) { if (v[i][j + 1] != '.') { if (v[i][j + 1] == v[i][j]) { if (qash < dist[i][j + 1]) { dist[i][j + 1] = qash; q.push({ -qash,{i,j + 1} }); } } else { qash++; if (qash < dist[i][j + 1]) { dist[i][j + 1] = qash; q.push({ -qash,{i,j + 1} }); } qash--; } } } if (i - 1 >= 0) { if (v[i - 1][j] != '.') { if (v[i - 1][j] == v[i][j]) { if (qash < dist[i - 1][j]) { dist[i - 1][j] = qash; q.push({ -qash,{i - 1,j} }); } } else { qash++; if (qash < dist[i - 1][j]) { dist[i - 1][j] = qash; q.push({ -qash,{i - 1,j} }); } qash--; } } } if (j - 1 >= 0) { if (v[i][j - 1] != '.') { if (v[i][j - 1] == v[i][j]) { if (qash < dist[i][j - 1]) { dist[i][j - 1] = qash; q.push({ -qash,{i,j - 1} }); } } else { qash++; if (qash < dist[i][j - 1]) { dist[i][j - 1] = qash; q.push({ -qash,{i,j - 1} }); } qash--; } } } } //for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // //cout << min(dist[i][j], 9) << " "; // if (v[i][j] != '.') { // mx = max(mx, dist[i][j]); // } // } // //cout << endl; //} cout << mx << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); ll t = 1; //cin >> t; while (t--) { solve(); } }