#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } using P = pair; using T = tuple; int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[] = {0, 0, 1, -1, 1, -1, 1, -1}; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int h, w; cin >> h >> w; vector s(h); for(int i = 0; i < h; i++) cin >> s[i]; auto ok = [&](int i, int j){ for(int x = 0; x < 3; x++){ for(int y = 0; y < 3; y++){ if(s[i+x][j+y] == '#') return false; } } return true; }; auto move_ok = [&](){ auto f = vec2d(h-2, w-2, true); for(int i = 0; i < h-2; i++){ for(int j = 0; j < w-2; j++){ f[i][j] = ok(i, j); } } auto in_field = [&](int x, int y){ return 0 <= x && x < h-2 && 0 <= y && y < w-2; }; auto dp = vec2d(h-2, w-2, false); queue

que; auto set_dp = [&](int x, int y){ if(!dp[x][y]){ dp[x][y] = true; que.push({x, y}); } }; set_dp(0, 0); while(!que.empty()){ auto [x, y] = que.front(); que.pop(); for(int k = 0; k < 8; k++){ int xx = x+dx[k]; int yy = y+dy[k]; if(!in_field(xx, yy)) continue; if(!f[xx][yy]) continue; set_dp(xx, yy); } } if(dp[h-3][w-3]) return true; return false; }; if(!move_ok()){ cout << 0 << endl; return 0; } for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(i <= 2 && j <= 2) continue; if(i >= h-3 && j >= w-3) continue; if(s[i][j] == '#') continue; s[i][j] = '#'; if(!move_ok()){ cout << 1 << endl; return 0; } s[i][j] = '.'; } } cout << 2 << endl; }