题目链接：局部极小值
这是一道\(dp\)好题。
由于需要保证某些位置比周围都要小，那么我们可以从小到大把每个数依次填入，保证每个局部极小值填入之前周围都不能填，就只需要在加入的时候计数了。
由于局部极小值最多只可能出现\(8\)个，所以我们可以直接状压当前所有局部极小值位置的状态。\(f_{i,S}\)表示当前填完了\(i\)个数，局部极小值状态为\(S\)的方案数。同时我们还需要一个\(cnt\)数组，\(cnt_S\)表示当局部极小值状态为\(S\)时有多少个位置不能填。
这样转移方程就很显然了。可以从\(f_{i,S}\)转到\(f_{i+1,S}\)，方案数为\(nm-i-cnt[S]\)；或者直接在某个局部极小值位置上填一个数。
但是这样会有问题，可能会导致某些非局部极小值的位置成为局部极小值。于是我们就可以枚举每个非局部极小值的位置是否是局部极小值，然后容斥掉即可。这样枚举的方案数看似很多，实际上最坏是不到\(2\times 10^4\)的。注意需要处理矩阵不合法的情况。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define mod 12345678 using namespace std;
typedef long long llg; int zx[8]={-1,0,1,1,1,0,-1,-1};
int zy[8]={1,1,1,0,-1,-1,-1,0};
int n,m,cnt[1<<8],tol,fr[1<<8];
int f[29][1<<8],op[1<<8],ans;
int ci[5][8],ax[8],ay[8],la;
char s[5][8]; void work(int x,int y,int S,int z){
for(int k=0,i,j;k<8;k++){
i=x+zx[k],j=y+zy[k];
if(i>0 && i<=n && j>0 && j<=m){
if(!ci[i][j]) cnt[S]++;
ci[i][j]+=z;
}
}
} void dp(){
int now=1<<la;
for(int S=0;S<now;S++){
cnt[S]=fr[S];
for(int x=S,j;j=x&(-x),x;x-=j)
work(ax[op[j]+1],ay[op[j]+1],S,1);
for(int x=S,j;j=x&(-x),x;x-=j)
work(ax[op[j]+1],ay[op[j]+1],S,-1);
}
for(int i=0;i<=n*m;i++)
for(int S=0;S<now;S++) f[i][S]=0;
f[0][now-1]=1;
for(int i=0;i<n*m;i++){
for(int S=0,x;S<now;S++){
(f[i+1][S]+=f[i][S]*(n*m-i-cnt[S]))%=mod;
for(x=S;x;x-=x&(-x))
(f[i+1][S^(x&(-x))]+=f[i][S])%=mod;
}
}
if(tol) (ans-=f[n*m][0])%=mod;
else (ans+=f[n*m][0])%=mod;
} void print(){printf("0");exit(0);}
void dfs(int x,int y){
if(y==m+1) x++,y=1;
if(x==n+1){dp();return;}
bool ww=s[x][y]=='.';
for(int k=0;k<8;k++)
if(s[x+zx[k]][y+zy[k]]=='X') ww=0;
if(ww) s[x][y]='X',tol++;
if(s[x][y]=='X'){
la++,ax[la]=x,ay[la]=y;
dfs(x,y+1),la--;
}
if(ww) s[x][y]='.',tol--;
if(s[x][y]=='.') dfs(x,y+1);
} int main(){
File("a");
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(s[i][j]=='X')
for(int k=0;k<8;k++)
if(s[i+zx[k]][j+zy[k]]=='X') print();
for(int i=0;i<(1<<8);i++) fr[i]=fr[i>>1]+(i&1);
for(int i=0;i<8;i++) op[1<<i]=i; dfs(1,1);
printf("%d",(ans+mod)%mod);
return 0;
}