#include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; if(min(N,M) == 1){cout << "0\n"; return 0;} vector S(N); for(auto &s : S) cin >> s; auto chmax = [&](int &a,int b) -> void {a=max(a,b);}; int K = 1<<(M*2+2),mask = K-1; vector P1(K),P2(K),P3(K); vector B1(K),B2(K),B3(K); for(int i=0; i>(M+1))&1) P1.at(i) = true; else{ int plant = 0; if((to>>(2*M+1))&1) plant++; if((to>>(2*M))&1) plant++; if((to>>M)&1) plant++; if((to>>1)&1) plant++; if((to>>0)&1) plant++; if(plant >= 2) P1.at(i) = true; } } { int to = i*2; if((to>>(M+1))&1) B1.at(i) = true; else{ int plant = 0; if((to>>(2*M+1))&1) plant++; if((to>>(2*M))&1) plant++; if((to>>M)&1) plant++; if((to>>1)&1) plant++; if((to>>0)&1) plant++; if(plant >= 2) B1.at(i) = true; } } { int to = i*2+1; if((to>>(M+1))&1) P2.at(i) = true; else{ int plant = 0; if((to>>(2*M+2))&1) plant++; if((to>>(2*M+1))&1) plant++; if((to>>(2*M))&1) plant++; if((to>>(M+2))&1) plant++; if((to>>M)&1) plant++; if((to>>2)&1) plant++; if((to>>1)&1) plant++; if((to>>0)&1) plant++; if(plant >= 2) P2.at(i) = true; } } { int to = i*2; if((to>>(M+1))&1) B2.at(i) = true; else{ int plant = 0; if((to>>(2*M+2))&1) plant++; if((to>>(2*M+1))&1) plant++; if((to>>(2*M))&1) plant++; if((to>>(M+2))&1) plant++; if((to>>M)&1) plant++; if((to>>2)&1) plant++; if((to>>1)&1) plant++; if((to>>0)&1) plant++; if(plant >= 2) B2.at(i) = true; } } { int to = i*2+1; if((to>>(M+1))&1) P3.at(i) = true; else{ int plant = 0; if((to>>(2*M+2))&1) plant++; if((to>>(2*M+1))&1) plant++; if((to>>(M+2))&1) plant++; if((to>>2)&1) plant++; if((to>>1)&1) plant++; if(plant >= 2) P3.at(i) = true; } } { int to = i*2; if((to>>(M+1))&1) B3.at(i) = true; else{ int plant = 0; if((to>>(2*M+2))&1) plant++; if((to>>(2*M+1))&1) plant++; if((to>>(M+2))&1) plant++; if((to>>2)&1) plant++; if((to>>1)&1) plant++; if(plant >= 2) B3.at(i) = true; } } } vector dp(K,-1); dp.at(0) = 0; for(int x=0; x 1 || (x == 1 && y >= 1)){ if(y == 0) check = S.at(x-2).at(M-1); else check = S.at(x-1).at(y-1); } vector next(K,-1); if(S.at(x).at(y) == '.'){ int fire = 0; for(int dx=-1; dx<=1; dx++) for(int dy=-1; dy<=1; dy++){ int nx = x+dx,ny = y+dy; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(S.at(nx).at(ny) == '#') fire++; } if(check == '.'){ if(fire >= 2){ for(int i=0; i= 2){ for(int i=0; i>d)&1) continue; int plant = 0; if(y == 0){ if((i>>(d+M))&1) plant++; if((i>>(d+M-1))&1) plant++; if((i>>(d-1))&1) plant++; } else if(y == M-1){ if((i>>(d+M+1))&1) plant++; if((i>>(d+M))&1) plant++; if((i>>(d+1))&1) plant++; } else{ if((i>>(d+M+1))&1) plant++; if((i>>(d+M))&1) plant++; if((i>>(d+M-1))&1) plant++; if((i>>(d+1))&1) plant++; if((i>>(d-1))&1) plant++; } if(plant < 2){ok = false; break;} } if(ok) answer = max(answer,v); } } cout << answer << endl; }