#include #ifdef LOCAL #include #else #define debug(...) void(0) #endif using namespace std; typedef long long ll; #define all(x) begin(x), end(x) constexpr int INF = (1 << 30) - 1; constexpr long long IINF = (1LL << 60) - 1; template istream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { auto sep = ""; for (const auto& x : v) os << exchange(sep, " ") << x; return os; } template bool chmin(T& x, U&& y) { return y < x and (x = forward(y), true); } template bool chmax(T& x, U&& y) { return x < y and (x = forward(y), true); } template void mkuni(vector& v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template int lwb(const vector& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector S(H); for (auto& s : S) cin >> s; vector ok(H, vector(W, false)), dp(H, vector(W, false)); auto check = [&]() { for (int x = 1; x < H - 1; x++) { for (int y = 1; y < W - 1; y++) { ok[x][y] = true; dp[x][y] = false; } } for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { if (S[x][y] != '#') continue; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { int nx = x + dx, ny = y + dy; if (nx < 0 or H <= nx or ny < 0 or W <= ny) continue; ok[nx][ny] = false; } } } } queue> que; dp[1][1] = true; que.emplace(1, 1); while (not que.empty()) { auto [x, y] = que.front(); que.pop(); for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { int nx = x + dx, ny = y + dy; if (nx < 0 or H <= nx or ny < 0 or W <= ny) continue; if (not ok[nx][ny]) continue; if (dp[nx][ny]) continue; dp[nx][ny] = true; que.emplace(nx, ny); } } } return dp[H - 2][W - 2]; }; if (not check()) { cout << 0 << '\n'; return 0; } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '#') continue; S[i][j] = '#'; if (not check()) { cout << 1 << '\n'; return 0; } S[i][j] = '.'; } } cout << 2 << '\n'; return 0; }