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(); }