#include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; int W, H; char G[22][22]; int F[22][22]; bool vis[22][22]; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; inline bool valid(int x, int y) { return 0<=x&&x> q; q.emplace(x, y); vis[y][x] = 1; while(!q.empty()) { F[y][x] = key; x = q.front().first, y = q.front().second; q.pop(); rep(k, 4) { int nx = x+dx[k], ny = y+dy[k]; if(!valid(nx, ny) || !balid(nx, ny)) { continue; } if(vis[ny][nx]) { continue; } vis[y][x] = 1; q.emplace(nx, ny); } } } int main() { cin >> W >> H; rep(i, H) rep(j, W) { cin >> G[i][j]; } int key = 1; rep(i, H) rep(j, W) { if(G[i][j] == '.' && F[i][j] == 0) { bfs(j, i, key++); } } int ans = 1<<29; rep(i, H) rep(j, W) { if(F[i][j] == 1) { rep(k, H) rep(l, W) { if(F[k][l] == 2) { ans = min(ans, abs(k-i)+abs(l-j)-1); } } } } cout << ans << endl; return 0; }