#include using namespace std; #define int long long struct Unionfind{ vector par, siz; //初期化 Unionfind(int n) : par(n,-1) , siz(n,1) {} int root(int x) { if(par[x] == -1) return x; else return par[x] = root(par[x]); } bool issame(int x,int y) { return root(x) == root(y); } bool unite(int x, int y){ x = root(x); y = root(y); if(x == y) return false; if(siz[x] < siz[y]) swap(x,y); par[y] = x; siz[x] += siz[y]; return true; } int size(int x) { return siz[root(x)]; } }; signed main(){ int H,W; cin>>H>>W; vector> S(H,vector(W)); for(int i=0;i>S[i][j]; vector> A(H-2,vector(W-2,true)); for(int i=0;i= H-3 && j >= W-3)) continue; vector> B = A; for(int k=-2;k<=0;k++)for(int l=-2;l<=0;l++)if(i+k >= 0 && j+l >= 0 && i+k+2 < H && j+l+2 < W) B[i+k][j+l] = false; Unionfind uf((H-2)*(W-2)); for(int k=0;k= 0 && k+x < H-2 && l+y >= 0 && l+y < W-2 && B[k][l] && B[k+x][l+y]) uf.unite(k*(W-2)+l,(k+x)*(W-2)+(l+y)); } if(!uf.issame(0,(H-2)*(W-2)-1)) ans = 1; } Unionfind uf((H-2)*(W-2)); for(int k=0;k= 0 && k+x < H-2 && l+y >= 0 && l+y < W-2 && A[k][l] && A[k+x][l+y]) uf.unite(k*(W-2)+l,(k+x)*(W-2)+(l+y)); } if(!uf.issame(0,(H-2)*(W-2)-1)) ans = 0; cout<