AOJ 0236 Alien Messages

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0236
UAPC以来のAOJ。

概要は日本語の通り。

Devquizで結構頑張った経験を活かせたと思いたいです。
ハッシュで訪れた状態を二度訪れないようにしたり、よく分からない行き止まりが出来たりしたものや、あきらかにスタート地点まで戻れないものの枝を買っています。

最後は全て埋まっている盤面をYesと答えてしまいWAってました。

typedef struct _node{
  ll key;
  _node *next;
}node;


const int hashMod=437935;
node ent[10000000];
int sz;
node* hash[hashMod];

void insert(ll key){
  int ha=key%hashMod;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key)return;
  }
  node*p=hash[ha];
  hash[ha]=ent+sz++;
  hash[ha]->key=key;
  hash[ha]->next=p;
}

bool count(ll key){
  int ha=key%hashMod;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key)return true;
  }
  return false;
}

int n,m;
int sx,sy;

bool get(ll st,int x,int y){
  return (st>>x*m+y)&1;
}

void pr(ll st,int x,int y){
  rep(i,n){
    rep(j,m){
      if(i==x && j==y)cout<<2<<' ';
      else cout<<get(st,i,j)<<' ';
    }
    cout<<endl;
  }
  cout<<endl;
}

bool cancut(ll st,int x,int y){
  //pr(st,x,y);
  rep(i,n)rep(j,m){
    if((i==sx && j==sy) ||
       get(st,i,j))continue;
    int ne0=0;
    rep(k,4){
      int nx=i+dx[k],ny=j+dy[k];
      if((0>nx || nx>=n ||
         0>ny || ny>=m ||
          get(st,nx,ny)) &&
         nx!=x && ny!=y)continue;
      ++ne0;
    }
    if(ne0<2){
      //cout<<i<<' '<<j<<' '<<ne0<<' '<<get(st,i,j)<<endl;
      //cout<<"true"<<endl;
      return true;
    }
  }
  //cout<<"false"<<endl;
  return false;
}

bool dfs(ll st,int x,int y,int b){
  //pr(st,x,y);
  if(abs(x-sx)+abs(y-sy)>b)return false;  
  if(b==0 && x==sx && y==sy)return true;
  ll ast=st|ll(x)<<51LL|ll(y)<<56LL;
  if(count(ast))return false;
  insert(ast);

  if(cancut(st,x,y))return false;
  
  rep(i,4){
    int nx=x+dx[i],ny=y+dy[i];
    if(0>nx || nx>=n ||
       0>ny || ny>=m ||
       get(st,nx,ny))continue;
    ll nst=st|1LL<<nx*m+ny;
    if(dfs(nst,nx,ny,b-1))return true;
  }
  return false;
}

void solve(){
  sz=0;
  memset(hash,0,sizeof(hash));
  ll st=0;
  int bu=0;
  rep(i,n){
    rep(j,m){
      ll t;
      cin>>t;
      st|=t<<i*m+j;
      bu+=t;
    }
  }
  rep(i,n)rep(j,m){
    if(get(st,i,j))continue;
    sx=i;
    sy=j;
    break;
  }

  if(n*m!=bu && (n*m-bu)%2==0 && dfs(st,sx,sy,n*m-bu))cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

main(){
  while(cin>>m>>n,n|m)solve();
}