#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; } queue<pair<int, pair<int, int>>>q; vector<vector<int>>dist(n, vector<int>(m, 1e9)); int mx = 0; q.push({ -1,{0,0} }); dist[0][0] = 1; while (q.size()) { int i = q.front().second.first, j = q.front().second.second, qash = -q.front().first; q.pop(); if (qash != dist[i][j])continue; mx = max(mx, dist[i][j]); 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 (qash + (v[i][j - 1] != v[i][j]) < dist[i][j - 1]) { dist[i][j - 1] = qash + (v[i][j - 1] != v[i][j]); q.push({ -(qash + (v[i][j - 1] != v[i][j])),{i,j - 1} }); } } }*/ 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--; } } } } 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(); } }