#include using namespace std; int h, w; const int MAX = 30; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; char C[MAX][MAX]; bool seen[MAX][MAX]; int D[MAX][MAX]; struct UnionFind{ vector par; UnionFind(int N) : par(N){ for(int i = 0; i < N; i++){ par[i] = -1; } } int root(int x){ if(par[x] < 0) return x; else return par[x] = root(par[x]); } void unite(int x, int y){ int rx = root(x); int ry = root(y); if(rx == ry) return; else{ if(par[rx] == par[ry]){ if(rx > ry) swap(rx, ry); }else if(par[rx] > par[ry]) swap(rx, ry); par[rx] += par[ry]; par[ry] = rx; } } bool same(int x, int y){ return root(x) == root(y); } void check(){ for(auto x : par){ cout << x << " "; } cout << endl; } }; void dfs(int x, int y, UnionFind &uf){ seen[x][y] = true; for(int i = 0; i < 4; i++){ int nx, ny; nx = dx[i] + x; ny = dy[i] + y; if(nx < 0 or ny < 0 or nx >= h or ny >= w) continue; if(C[nx][ny] == '#' or seen[nx][ny]) continue; uf.unite(x * w + y, nx * w + ny); dfs(nx, ny, uf); } return; } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> w >> h; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin >> C[i][j]; D[i][j] = 1e9; } } UnionFind uf(h * w); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(C[i][j] == '.'){ if(!seen[i][j]){ dfs(i, j, uf); } } } } queue> q; bool f = true; int bp; for(int i = 1; i < h - 1; i++){ for(int j = 1; j < w - 1; j++){ if(C[i][j] == '#') continue; int r = uf.root(i * w + j); if(f and uf.par[r] != -1){ bp = r; f = false; q.push({i, j}); }else if(!f and r == bp){ q.push({i, j}); } } } int ans = 1e9; while(!q.empty()){ pair p = q.front(); int px, py; px = p.first; py = p.second; D[px][py] = 0; queue> qq; for(int i = 0; i < 4; i++){ int nx, ny; nx = px + dx[i]; ny = py + dy[i]; if(nx < 0 or ny < 0 or nx >= h or ny >= w) continue; if(C[nx][ny] == '#'){ qq.push({nx, ny}); D[nx][ny] = 1; } } while(!qq.empty()){ pair pp = qq.front(); qq.pop(); int ppx, ppy; ppx = pp.first; ppy == pp.second; for(int i = 0; i < 4; i++){ int nx, ny; nx = px + dx[i]; ny = py + dy[i]; if(nx < 0 or ny < 0 or nx >= h or ny >= w) continue; if(C[nx][ny] == '.'){ if(!(uf.same(bp, nx * w + ny))){ ans = min(ans, D[ppx][ppy]); } }else{ if(D[ppx][ppy] + 1 < D[nx][ny]){ D[nx][ny] = D[ppx][ppy] + 1; qq.push({nx, ny}); } } } } } cout << ans << endl; /* for(int i = 0; i < h * w; i++){ cout << uf.par[i] << ' '; if((i + 1) % w == 0) cout << endl; } */ return 0; }