#include #include #include #include using namespace std; const vector dx = { -1, -1, -1, 0, 0, 1, 1, 1 }; const vector dy = { -1, 0, 1, -1, 1, -1, 0, 1 }; bool reachable(int H, int W, const vector& S) { vector > flag(H - 2, vector(W - 2, true)); for (int i = 0; i < H - 2; i++) { for (int j = 0; j < W - 2; j++) { for (int k = 0; k < 3; k++) { for (int l = 0; l < 3; l++) { if (S[i + k][j + l] == '#') { flag[i][j] = false; } } } } } vector > vis(H - 2, vector(W - 2, false)); auto dfs = [&](auto& dfs, int x, int y) -> void { vis[x][y] = true; for (int i = 0; i < 8; i++) { int tx = x + dx[i]; int ty = y + dy[i]; if (0 <= tx && tx < H - 2 && 0 <= ty && ty < W - 2 && flag[tx][ty] && !vis[tx][ty]) { dfs(dfs, tx, ty); } } }; dfs(dfs, 0, 0); return vis[H - 3][W - 3]; } int main() { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } if (!reachable(H, W, S)) { cout << 0 << endl; } else { bool flag = false; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '.' && !(i < 3 && j < 3) && !(i >= H - 3 && j >= W - 3)) { S[i][j] = '#'; if (!reachable(H, W, S)) { flag = true; } S[i][j] = '.'; } } } cout << (flag ? 1 : 2) << endl; } return 0; }