#ifndef hari64 #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define debug(...) #else #include "util/viewer.hpp" #define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__) #endif // clang-format off using namespace std; using ll = long long; using ld = long double; using pii = pair; using pll = pair; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; using vi = vc; using vll = vc; using vpii = vc; using vpll = vc; using vvi = vc; using vvll = vc; using vvpi = vc; using vvpll = vc; #define ALL(x) begin(x), end(x) #define RALL(x) (x).rbegin(), (x).rend() constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001; template bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } // clang-format on int H, W; vector Ss; bool canReach() { vector> grid(H - 2, vector(W - 2, INF)); for (int h = 1; h < H - 1; h++) { for (int w = 1; w < W - 1; w++) { grid[h - 1][w - 1] = true; for (int dh = -1; dh <= 1; dh++) { for (int dw = -1; dw <= 1; dw++) { if (Ss[h + dh][w + dw] == '#') { grid[h - 1][w - 1] = false; } } } } } assert(grid[0][0] == true && grid[H - 3][W - 3] == true); // 0,0からH-3,W-3までの経路があるか vector> dp(H - 2, vector(W - 2, false)); dp[0][0] = true; for (int h = 0; h < H - 2; h++) { for (int w = 0; w < W - 2; w++) { if (!dp[h][w]) continue; if (grid[h][w]) { if (h + 1 < H - 2 && grid[h + 1][w]) dp[h + 1][w] = true; if (w + 1 < W - 2 && grid[h][w + 1]) dp[h][w + 1] = true; } } } return dp[H - 3][W - 3]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W; assert(6 <= H && 6 <= W); assert(H * W <= 2400); Ss.resize(H); for (auto& S : Ss) { cin >> S; assert(int(S.size()) == W); for (auto& c : S) { assert(c == '.' || c == '#'); } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { assert(Ss[i][j] == '.'); } } for (int i = H - 3; i < H; i++) { for (int j = W - 3; j < W; j++) { assert(Ss[i][j] == '.'); } } int ans = 2; if (!canReach()) { ans = 0; } else { for (int h = 0; h < H && ans == 2; h++) { for (int w = 0; w < W && ans == 2; w++) { if (h < 3 && w < 3) continue; if (h >= H - 3 && w >= W - 3) continue; if (Ss[h][w] == '#') continue; Ss[h][w] = '#'; if (!canReach()) { ans = 1; } Ss[h][w] = '.'; } } } cout << ans << endl; return 0; }