一开始看范围特别小就写搜索了。。。结果自己随便出了个4*4就过不了了。。
其实就是状态压缩DP，求哈密顿回路要多少条，只是要注意判断两点是否可以划线就可以了。
#include <stdio.h> #include <string.h> #include <algorithm> typedef __int64 LL; int n,m,tot; int mz[25],bet[25][25][25],full; int zero[16],zeros,hzero[25],lowb[65536]; LL d[16][65536],ans; int cant(int st,int en,int stat){ st=zero[st],en=zero[en]; if(st>en)std::swap(st,en); for(int i=1;i<=bet[st][en][0];i++){ int x=bet[st][en][i]; if(mz[x]==1)return 1; if(mz[x]==0&&((stat>>hzero[x])&1)==0)return 1; } return 0; } LL dp(int last,int stat){ if(d[last][stat]!=-1)return d[last][stat]; if(stat==(stat&-stat))return 1; LL nans=0; int nstat=stat,now,i; while(nstat){ now=(nstat&-nstat),i=lowb[now],nstat-=now;; if(i==last||cant(i,last,stat))continue; nans+=dp(i,stat&~(1<<last)); } return d[last][stat]=nans; } int between(int k,int i,int j,int n,int m){ int xk=k/m,yk=k%m,xi=i/m,yi=i%m,xj=j/m,yj=j%m; if((xk-xi)*(xk-xj)<=0&&(yk-yi)*(yk-yj)<=0){ if((yj-yi)*(xk-xi)==(xj-xi)*(yk-yi))return 1; } return 0; } void init(int n,int m){ for(int i=0;i<tot;i++){ for(int j=i+1;j<tot;j++){ int &x=bet[i][j][0];x=0; for(int k=i+1;k<j;k++){ if(between(k,i,j,n,m))x++,bet[i][j][x]=k; } } } for(int i=0,x=1;i<16;i++,x<<=1)lowb[x]=i; } int main(){ // freopen("test.in","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ ans=0,tot=n*m,zeros=0; init(n,m); for(int i=0;i<tot;i++){ scanf("%d",&mz[i]); if(mz[i]==0)hzero[i]=zeros,zero[zeros++]=i; } full=(1<<zeros)-1; for(int i=0;i<zeros;i++)for(int j=0;j<=full;j++)d[i][j]=-1; for(int i=0;i<zeros;i++)ans+=dp(i,full); printf("%I64d\n",ans); } return 0; }