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