#include using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template bool chmax(T &a, const T &b) { if(a bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- int H,W; string S[2424]; int ok[2424][2424]; int D[2424][2424]; int hoge() { int y,x,dy,dx; FOR(y,H-2) FOR(x,W-2) { D[y][x]=0; ok[y][x]=1; for(dy=y;dy<=y+2;dy++) for(dx=x;dx<=x+2;dx++) if(S[dy][dx]=='#') ok[y][x]=0; } D[0][0]=1; queue Q; Q.push(0); while(Q.size()) { int cy=Q.front()/10000; int cx=Q.front()%10000; Q.pop(); if(cy==H-3&&cx==W-3) return 0; for(y=cy-1;y<=cy+1;y++) for(x=cx-1;x<=cx+1;x++) { if(x<0||x>W-3||y<0||y>H-3) continue; if(ok[y][x]==0) continue; if(D[y][x]==1) continue; D[y][x]=1; Q.push(y*10000+x); } } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(y,H) cin>>S[y]; if(hoge()) { cout<<0<=H-3&&x>=H-3) continue; S[y][x]='#'; if(hoge()) { cout<<1<