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