#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 dist[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> W >> H; rep(i, H) rep(j, W) { cin >> G[i][j]; if(G[i][j] == '.') { sx = j, sy = i; } } std::queue> q; q.emplace(sx, sy); rep(i, 22) rep(j, 22) dist[i][j] = 1<<29; dist[sy][sx] = 0; while(!q.empty()) { int x = std::get<0>(q.front()); int y = std::get<1>(q.front()); q.pop(); rep(k, 4) { int nx = x+dx[k], ny = y+dy[k]; if(!valid(nx, ny)) { continue; } int nc = dist[y][x]+(G[ny][nx]=='#'); if(dist[ny][nx] <= nc) { continue; } dist[ny][nx] = nc; q.emplace(nx, ny); } } rep(i, H) rep(j, W) { if(G[i][j] == '.' && dist[i][j]) { cout << dist[i][j] << endl; return 0; } } return 0; }