#include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <random> #include <vector> #include <algorithm> #include <array> #include <functional> #include <utility> #include <regex> #include <tuple> #include <map> #include <set> #include <iostream> using namespace std; int main(){ int h,w; -scanf("%d%d",&w,&h); vector<string> c(h); vector<array<int,2>> a,b,q; vector<int> f(w*h,0x7fffffff); for(int y=0;y<h;y++){ cin>>c[y]; for(int x=0;x<w;x++){ if(c[y][x]=='.'){ a.push_back(array<int,2>({x,y})); } } } b.push_back(a.back()); q.push_back(a.back()); a.pop_back(); while(q.size()){ int cnt=0; array<int,2> s=q[q.size()-1]; s[0]--; auto it=find(a.begin(),a.end(),s); s[0]++; if(it!=a.end()){ b.push_back(*it); q.push_back(*it); a.erase(it); cnt++; } s=q[q.size()-1]; s[0]++; it=find(a.begin(),a.end(),s); s[0]--; if(it!=a.end()){ b.push_back(*it); q.push_back(*it); a.erase(it); cnt++; } s=q[q.size()-1]; s[1]--; it=find(a.begin(),a.end(),s); s[1]++; if(it!=a.end()){ b.push_back(*it); q.push_back(*it); a.erase(it); cnt++; } s=q[q.size()-1]; s[1]++; it=find(a.begin(),a.end(),s); s[1]--; if(it!=a.end()){ b.push_back(*it); q.push_back(*it); a.erase(it); cnt++; } if(cnt==0) q.pop_back(); } int manhattan_min=0x7fffffff; for(auto i:a){ for(auto j:b){ manhattan_min=min(manhattan_min,abs(i[0]-j[0])+abs(i[1]-j[1])-1); } } cout<<manhattan_min<<endl; return 0; }