题意
有一个 \(n\times m\) 的矩阵，其中每个数都是 \([1,n\times m]\) 中的一个，不会重复。有一些地方的值比周围的8个位置都小（如果有的话）。给出这些位置，求这样的矩阵有多少个。
\(n\le 4,m\le 7\) 。
分析
一个很关键的信息是局部极小值的点最多只有8个，以及每个数都不会重复。
这种有大小关系的填数问题，我们可以考虑从小到大填每个数。如果能够确定当前限制点的填写情况（是否填了），那么我们就能知道当前的决策有多少个可行位置。因为我们是从小到大填每个数，所以每个数的每个位置都是一种方案。
状态压缩当前限制的填写情况，预处理在一种填写状态下有多少个位置能填，我们就可以通过分当前这个数填在限制位置还是非限制位置进行dp。
然而会有一些不合法的情况，原因是没有限制的位置我们随便乱填之后可能会出现局部极小值，所以我们要把这些情况减掉。所以使用容斥原理减少限制——保证有某一些为局部极小值，其他不管，进行容斥。我们进行dfs，有哪些位置保证为局部极小值。
单次dp的复杂度为 \((2^Xnm)\) ，dfs剪枝能够通过。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long giant;
const int xx[]={-1,-1,-1,0,1,1,1,0};
const int yy[]={-1,0,1,1,1,0,-1,-1};
const int maxn=5;
const int maxm=8;
const int maxx=8;
const int maxs=1<<maxx;
const int q=12345678;
inline int Plus(int x,int y) {return ((giant)x+(giant)y)%q;}
inline int Multi(int x,int y) {return (giant)x*y%q;}
int n,m,ans=0,p[maxx][2],cnt[maxs],f[maxn*maxm][maxs],nm,ord=0;
bool a[maxn][maxm],mp[maxn][maxm];
inline int nxtx(int x,int y) {return x+(y==m);}
inline int nxty(int x,int y) {return y==m?1:y+1;}
void dp() {
int g=0,s;
for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (a[i][j]) {
for (int k=0;k<8;++k) {
int x=i+xx[k],y=j+yy[k];
if (x>0 && y>0 && x<=n && y<=m && a[x][y]) return;
}
p[g][0]=i,p[g][1]=j;
++g;
}
s=1<<g;
memset(cnt,0,sizeof cnt);
for (int j=0;j<s;++j) {
memset(mp,0,sizeof mp);
for (int i=0;i<g;++i) if (!((j>>i)&1)) {
mp[p[i][0]][p[i][1]]|=true;
for (int k=0;k<8;++k) {
int x=p[i][0]+xx[k],y=p[i][1]+yy[k];
if (x>0 && y>0 && x<=n && y<=m) mp[x][y]|=true;
}
}
for (int i=1;i<=n;++i) for (int k=1;k<=m;++k) cnt[j]+=(!mp[i][k]);
}
memset(f,0,sizeof f);
f[0][0]=1;
for (int i=1;i<=nm;++i) for (int j=0;j<s;++j) {
if (cnt[j]>i-1) f[i][j]=Multi(f[i-1][j],cnt[j]-i+1);
for (int k=0;k<g;++k) if ((j>>k)&1) f[i][j]=Plus(f[i][j],f[i-1][j^(1<<k)]);
}
ans=Plus(ans,(g-ord)&1?q-f[nm][s-1]:f[nm][s-1]);
}
void dfs(int x,int y) {
if (x>n) {
dp();
return;
}
dfs(n+1,1);
for (int i=nxtx(x,y),j=nxty(x,y);i<=n;x=i,y=j,i=nxtx(x,y),j=nxty(x,y)) if (!a[i][j]) {
bool flag=true;
for (int k=0;k<8;++k) {
int x=i+xx[k],y=j+yy[k];
if (x>0 && y>0 && x<=n && y<=m && a[x][y]) {
flag=false;
break;
}
}
if (!flag) continue;
a[i][j]=true;
dfs(i,j);
a[i][j]=false;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
scanf("%d%d",&n,&m),nm=n*m;
for (int i=1;i<=n;++i) {
static char s[maxm+2];
scanf("%s",s+1);
for (int j=1;j<=m;++j) if (s[j]=='X') a[i][j]=true,++ord;
}
dfs(1,0);
printf("%d\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/7373885.html
