数据这么小，不是暴力就是状压。
考虑状压dp，f[i][j]表示前i大的数填完后，状态集合为j的情况。
这样我们可以从小到大填数。对于状态更新。
首先如果当前i我们填在一个谷底那么就是状态直接相加。
比较复杂的情况是我们填在非谷地，因为我们要知道还可以填哪些位置，而这些位置是随便填的，只要根据乘法原理乘一下就能更新
首先如果一个非谷地旁边是谷底，那么不能填，如果已经被填过了，那么也不能填，我们需要预处理这些状态可以看我的代码理解。
但是这样求出来并不是答案，因为我们现在满足的是谷地一定填好了，但是非谷地可能在更新中成为谷地，这个意思是说，我们更新的时候是根据乘法原理更新的
这里就会存在某个被定义为非谷地的点周围填的数都比他大，这样它就成为谷地了，但是这样是非法的，因此我们考虑去重。
一般这种去重很容易想到容斥原理，将某个可能成为谷地的非谷地人为设计为谷底，之后根据奇偶改变量决定是加还是减，这是容斥的基本套路
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pll; const int N=5e5+10; const int inf=0x3f3f3f3f; const int mod=772002; int n,m; int f[30][1200]; char g[30][30]; char tmp[30][30]; map<int,pll> m1; int pos[N],mou[N]; ll ans; int dx[]={-1,-1,0,1,1,1,0,-1}; int dy[]={0,1,1,1,0,-1,-1,-1}; int sx[N],sy[N]; bool check(){ int i,j; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(g[i][j]!='X') continue; for(int k=0;k<8;k++){ int x=i+dx[k]; int y=j+dy[k]; if(x&&x<=n&&y&&y<=m){ if(g[x][y]=='X') return true; } } } } return false; } ll solve(){ int i,j; memset(f,0,sizeof f); f[0][0]=1; int cnt=0; int num=n*m; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(g[i][j]=='X'){ cnt++; sx[cnt-1]=i; sy[cnt-1]=j; } } } memset(tmp,'.',sizeof tmp); int mx=1<<cnt; for(i=0;i<mx;i++){ mou[i]=0; for(j=0;j<cnt;j++){ if(i>>j&1){ mou[i]++; } else{ tmp[sx[j]][sy[j]]='Y'; } } pos[i]=num-cnt; for(int l=1;l<=n;l++){ for(int r=1;r<=m;r++){ if(g[l][r]=='X') continue; for(int k=0;k<8;k++){ int a=l+dx[k]; int b=r+dy[k]; if(a<=n&&a&&b&&b<=m){ if(tmp[a][b]=='Y'){ pos[i]--; break; } } } } } for(int k=0;k<cnt;k++){ tmp[sx[k]][sy[k]]='.'; } } for(i=0;i<num;i++){ for(j=0;j<mx;j++){ if(!f[i][j]) continue; for(int k=0;k<cnt;k++){ if(!((j>>k)&1)){ f[i+1][j|(1<<k)]=(f[i+1][j|(1<<k)]+f[i][j])%mod; } } f[i+1][j]=(f[i+1][j]+f[i][j]*(pos[j]-i+mou[j])%mod)%mod; } } return f[num][mx-1]; } void dfs(int u,int num){ if(u==n*m+1){ if(num%2==0) ans=(ans+solve())%mod; else ans=(ans-solve()+mod)%mod; return ; } int x=m1[u].first; int y=m1[u].second; int i; for(i=0;i<8;i++){ int a=x+dx[i]; int b=y+dy[i]; if(a&&a<=n&&b&&b<=m){ if(g[a][b]=='X') break; } } if(i==8&&g[x][y]=='.'){ g[x][y]='X'; dfs(u+1,num+1); g[x][y]='.'; } dfs(u+1,num); } int main(){ ios::sync_with_stdio(false); int times=1; while(cin>>n>>m){ m1.clear(); int i,j; int id=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>g[i][j]; m1[++id]={i,j}; } } if(check()){ cout<<"Case #"<<times++<<": "; cout<<0<<endl; } else{ ans=0; dfs(1,0); cout<<"Case #"<<times++<<": "; cout<<ans<<endl; } } return 0; }