因为X的个数不超过9所以我们压X的个数就行，然后从小到大分配数字，但是如果‘.'变成了山谷怎么办，所以我们容斥搜出'.'变成X的所有情况，情况也不超过2^9,然后就写完了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1<<9; const int mod=772002; char c[26][26]; int dp[26][maxn]; int a[8]={-1,-1,-1,0,1,1,1,0}; int b[8]={-1,0,1,1,1,0,-1,-1}; int n,m; int id[26][26]; int cnt[maxn]; int nn[maxn]; int cal(int p){ dp[0][0]=1; int w=1<<p; for(int i=0;i<w;i++){ cnt[i]=0; for(int j=0;j<n;j++){ for(int f=0;f<m;f++){ if(c[j][f]=='.'){ int flag=0; for(int u=0;u<8;u++){ int x=j+a[u]; int y=f+b[u]; if(x>=0&&x<n&&y>=0&&y<m){ if(c[x][y]=='X'&&(i&(1<<id[x][y]))==0){ flag=1; break; } } } cnt[i]+=flag^1; } } } } for(int i=1;i<=n*m;i++){ for(int j=0;j<w;j++){ dp[i][j]=((LL)dp[i-1][j]*(cnt[j]-(i-1-nn[j])))%mod; for(int q=0;q<p;q++){ if(j&(1<<q)){ dp[i][j]+=dp[i-1][j^(1<<q)]; dp[i][j]%=mod; } } } } return dp[n*m][w-1]; } int dfs(int x,int y,int t,int p){ int ans=0; if(x==n){ cal(p); if(t%2==0){ return cal(p); } else return (mod-cal(p))%mod; } if(y==m) return dfs(x+1,0,t,p); if(c[x][y]=='X'){ id[x][y]=p; return dfs(x,y+1,t,p+1); } int flag=0; for(int i=0;i<8;i++){ int x1=x+a[i]; int y1=y+b[i]; if(x1>=0&&x1<n&&y1>=0&&y1<m&&c[x1][y1]=='X'){ flag=1; } } ans=dfs(x,y+1,t,p); if(flag==0){ id[x][y]=p; c[x][y]='X'; ans+=dfs(x,y+1,t+1,p+1); ans%=mod; c[x][y]='.'; id[x][y]=0; } return ans; } int main() { int N=0; for(int i=1;i<maxn;i++) nn[i]=nn[i&(i-1)]+1; while (scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",c[i]); int flag=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(c[i][j]=='X'){ for(int f=0;f<8;f++){ int x=i+a[f]; int y=j+b[f]; if(x>=0&&x<n&&y>=0&&y<m){ if(c[x][y]=='X'){ flag=1; } } } } } } printf("Case #%d: ",++N); if(flag) printf("0\n"); else{ printf("%d\n",dfs(0,0,0,0)); } } }