#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; const int di[] = {1, 0, -1, 0}; const int dj[] = {0, 1, 0, -1}; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector s(n); rep(i, n) cin >> s[i]; auto check = [&]() -> bool { static vector s2; const int n2 = n - 2, m2 = m - 2; s2.resize(n2); rep(i, n2) s2[i].resize(m2, '.'); rep(i, n2) rep(j, m2) { s2[i][j] = [&] { rep(di, 3) rep(dj, 3) if (s[i+di][j+dj] == '#') { return '#'; } return '.'; }(); } assert(s2[0][0] == '.' && s2[n2-1][m2-1] == '.'); queue

q; q.emplace(0, 0); s2[0][0] = '#'; auto idxchk = [&](int i, int j) { return 0 <= i && i < n2 && 0 <= j && j < m2; }; while(q.size()) { auto [i, j] = q.front(); q.pop(); rep(k, 4) { int ni = i + di[k], nj = j + dj[k]; if (!idxchk(ni, nj)) continue; if (s2[ni][nj] == '.') { q.emplace(ni, nj); s2[ni][nj] = '#'; } } } return s2[n2-1][m2-1] == '#'; }; if (!check()) { cout << 0 << '\n'; return 0; } rep(i, n) rep(j, m) if (s[i][j] == '.') { if (i < 3 && j < 3) continue; if (i >= n - 3 && j >= m - 3) continue; s[i][j] = '#'; if (!check()) { cout << 1 << '\n'; return 0; } s[i][j] = '.'; } cout << 2 << '\n'; return 0; }