#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<int,int> #define all(a) a.begin(), a.end() #define el '\n' const int maxN = 4005; const int base = 311; const int MOD = 1e9+7; const int INF = 1e18; const int NEG_INF = -1e18; const int MAX_DAYS = 1000; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, 0, -1, 1}; int n, m, k, q, x; string S, T; int dist[maxN][maxN], par[maxN]; bool visited[maxN][maxN]; vector<int> g[maxN]; string grid[maxN]; // void bfs(int s){ // fill_n(dist, n + 1, -1); // fill_n(visited, n + 1, false); // fill_n(par, n + 1, -1); // queue<int> q; // q.push(s); // visited[s] = true; // dist[s] = 1; // while(!q.empty()){ // int u = q.front(); // q.pop(); // for(auto v : g[u]){ // if(!visited[v]){ // dist[v] = dist[u] + 1; // par[v] = u; // visited[v] = true; // q.push(v); // } // } // } // } bool inside(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= m && grid[x][y] != '.'); } int bfs_01() { int ans = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ dist[i][j] = INF; } } deque<pii> q; q.push_front({1,1}); dist[1][1] = 1; while(!q.empty()){ auto[x,y] = q.front(); q.pop_front(); ans = max(ans, dist[x][y]); for(int k = 0; k < 4; k++){ int nxt_x = x + dx[k], nxt_y = y + dy[k]; if(!inside(nxt_x, nxt_y)) continue; int w = (grid[x][y] == grid[nxt_x][nxt_y]) ? 0 : 1; if(dist[nxt_x][nxt_y] > dist[x][y] + w){ dist[nxt_x][nxt_y] = dist[x][y] + w; if(w == 1) q.push_back({nxt_x, nxt_y}); else q.push_front({nxt_x, nxt_y}); } } } return ans; } // void Trace(int u){ // vector<int> path; // while(u > 0){ // path.push_back(u); // u = par[u]; // } // reverse(path.begin(), path.end()); // for(int u : path) cout << u << " "; // } void run_test() { cin >> n >> m; for(int i = 1; i <= n; i++){ string s; cin >> s; s = '_' + s; grid[i] = s; } cout << bfs_01() << endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("pieaters.in", "r", stdin); // freopen("pieaters.out", "w", stdout); int test = 1; // cin >> test; while (test-- > 0) { run_test(); } }