#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_multiset = tree< T, null_type, std::less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve() { int h, w; cin >> h >> w; vector<string> grid(h); for (int i = 0; i < h; i++) cin >> grid[i]; vector dist(h, vector<int>(w, 1e9)); deque<pair<int, int>> d; dist[0][0] = 1; d.emplace_back(0, 0); vector<int> dx{0, 0, 1, -1}; vector<int> dy{1, -1, 0, 0}; while (!d.empty()) { auto [x, y] = d.front(); d.pop_front(); for (int i = 0; i < 4; i++) { int _x = x + dx[i], _y = y + dy[i]; if (_x < 0 || _x >= h || _y < 0 || _y >= w || grid[_y][_x] == '.') continue; int distance = dist[y][x]; if (grid[_y][_x] != grid[y][x]) distance++; if (dist[_y][_x] <= distance) continue; dist[_y][_x] = distance; if (distance == dist[y][x]) { d.emplace_front(_x, _y); } else d.emplace_back(_x, _y); } } int res = 0; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) res = max(res, dist[i][j] != 1e9 ? dist[i][j] : -1); cout << res << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); return 0; }