#include #include #include #include #include using namespace std; using pii = pair; int main() { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } queue que; vector> isvisited(H - 2, vector(W - 2, false)); que.push(pii(0, 0)); isvisited[0][0] = true; vector dx = {1, 1, 0, -1, -1, -1, 0, 1}; vector dy = {0, 1, 1, 1, 0, -1, -1, -1}; vector> pos(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 <= 2; k++) { for (int l = 0; l <= 2; l++) { if (S[i + k][j + l] == '#') { pos[i][j] = false; } } } } } while (que.size()) { pii p = que.front(); que.pop(); for (int i = 0; i < 8; i++) { if (p.first + dx[i] >= 0 && p.first + dx[i] < H - 2 && p.second + dy[i] >= 0 && p.second + dy[i] < W - 2) { if (isvisited[p.first + dx[i]][p.second + dy[i]]) { continue; } if (pos[p.first + dx[i]][p.second + dy[i]]) { isvisited[p.first + dx[i]][p.second + dy[i]] = true; que.push(pii(p.first + dx[i], p.second + dy[i])); } } } } if (!isvisited[H - 3][W - 3]) { cout << 0 << endl; return 0; } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '#') { continue; } if (i >= 0 && i <= 2 && j >= 0 && j <= 2) { continue; } if (i >= H - 3 && i < H && j >= W - 3 && j < W) { continue; } S[i][j] = '#'; que.push(pii(0, 0)); for (int k = 0; k < H - 2; k++) { for (int l = 0; l < W - 2; l++) { isvisited[k][l] = false; } } isvisited[0][0] = true; for (int k = 0; k < H - 2; k++) { for (int l = 0; l < W - 2; l++) { pos[k][l] = true; } } for (int k = 0; k < H - 2; k++) { for (int l = 0; l < W - 2; l++) { for (int m = 0; m < 3; m++) { for (int n = 0; n < 3; n++) { if (S[k + m][l + n] == '#') { pos[k][l] = false; } } } } } while (que.size()) { pii p = que.front(); que.pop(); for (int k = 0; k < 8; k++) { if (p.first + dx[k] >= 0 && p.first + dx[k] < H - 2 && p.second + dy[k] >= 0 && p.second + dy[k] < W - 2) { if (isvisited[p.first + dx[k]][p.second + dy[k]]) { continue; } if (pos[p.first + dx[k]][p.second + dy[k]]) { isvisited[p.first + dx[k]][p.second + dy[k]] = true; que.push(pii(p.first + dx[k], p.second + dy[k])); } } } } if (!isvisited[H - 3][W - 3]) { cout << 1 << endl; return 0; } S[i][j] = '.'; } } cout << 2 << endl; }