Tatami (AOJ2163)
枝刈り探索をします.(ちゃんと考察すると1次元DPにできる と解説には書いてあるが,結構難しい気がする)
おけない条件を点で考えるんじゃなくてななめで隣り合うところの置き方の問題として捉えるのが楽.
次にどこに置くべきか(候補が一番少ないところにする)を毎回H*W探索してるんだけどそれでも爆速だった 速すぎてこわいんだけど・・・ やっぱり枝刈りは闇.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; int H,W,ans; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; //drul bool cand[20][20][4]; bool done[20][20]; typedef vector<int> vi; void ers_(int x,int y,int d,vi &vx,vi &vy,vi &vd){ if(0<=x&&x<H&&0<=y&&y<W&&!done[x][y]&&cand[x][y][d]){ cand[x][y][d]=0; vx.pb(x),vy.pb(y),vd.pb(d); } } void ers(int x,int y,int d,vi &vx,vi &vy,vi &vd){ ers_(x,y,d,vx,vy,vd); ers_(x+dx[d],y+dy[d],(d+2)%4,vx,vy,vd); } bool ok(int x,int y){ return 0<=x&&x<H&&0<=y&&y<W&&!done[x][y]; } void dfs(int e,int f,int cnt){ // printf("cnt=%d %d,%d\n",cnt,e,f); // rep(i,H){ // rep(j,W) cout<<done[i][j]; // puts(""); // } if(cnt==H*W/2){ ans++; return; } rep(d,4) if(ok(e+dx[d],f+dy[d])&&cand[e][f][d]){ // show(d); vector<int> vx,vy,vd; int E=e+dx[d],F=f+dy[d]; int a=min(e,E),b=min(f,F),A=max(e,E),B=max(f,F); ers(a-1,b-1,2,vx,vy,vd); ers(a-1,b-1,3,vx,vy,vd); ers(a-1,B+1,2,vx,vy,vd); ers(a-1,B+1,1,vx,vy,vd); ers(A+1,b-1,0,vx,vy,vd); ers(A+1,b-1,3,vx,vy,vd); ers(A+1,B+1,0,vx,vy,vd); ers(A+1,B+1,1,vx,vy,vd); done[e][f]=1,done[E][F]=1; int nx=-1,ny=-1; { int mn=5; rep(x,H) rep(y,W) if(!done[x][y]){ int cs=0; rep(di,4) if(cand[x][y][di]) cs++; if(mn>cs){ mn=cs; nx=x,ny=y; } } } dfs(nx,ny,cnt+1); { //rmv done[a][b]=0,done[A][B]=0; rep(i,vx.size()){ cand[vx[i]][vy[i]][vd[i]]=1; } } } } int main(){ while(true){ cin>>H>>W; if(H==0) break; if(H*W%2){ puts("0"); continue; } ans=0; rep(i,H) rep(j,W){ cand[i][j][0]=(i!=H-1); cand[i][j][1]=(j!=W-1); cand[i][j][2]=(i!=0); cand[i][j][3]=(j!=0); } dfs(0,0,0); cout<<ans<<endl; } }