#include #include #include using namespace std; const int BUF = 25; const int INF = 1<<20; class QData{ public: int r, c, cost; QData(){} QData(int r, int c, int cost): r(r), c(c), cost(cost){} bool operator< (const QData &opp) const { return cost > opp.cost; } }; int row, col; string b[BUF]; void read() { cin >> col >> row; for (int i = 0; i < row; ++i) cin >> b[i]; } void work() { priority_queue Q; int cost[BUF][BUF]; for (int i = 0; i < BUF; ++i) for (int j = 0; j < BUF; ++j) cost[i][j] = INF; for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) { if (b[i][j] == '.') { cost[i][j] = 0; Q.push(QData(i, j, 0)); goto _finish; } } _finish: const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; while (!Q.empty()) { QData curr = Q.top(); Q.pop(); if (curr.cost > 0 && b[curr.r][curr.c] == '.') { cout << curr.cost << endl; break; } for (int i = 0; i < 4; ++i) { int nr = curr.r + dr[i]; int nc = curr.c + dc[i]; if (!(0 <= nr && nr < row && 0 <= nc && nc < col)) continue; int nexCost = curr.cost + (b[nr][nc] != '.'); if (cost[nr][nc] > nexCost) { cost[nr][nc] = nexCost; Q.push(QData(nr, nc, nexCost)); } } } } int main() { read(); work(); return 0; }