$\LARGE{分析}$
题目中要求的是恰好,利用容斥原理,把恰好换成至少,进行 $dp$
将 $1\sim nm$ 顺次填入,则若一个数比周围的数填入地更早,则其为局部极小值。
注意这里要对每一个局部极小值集合包含题目要求的分别进行一次 $dp$
设 $f_{i, s}$ 表示已经将 $1\sim i$ 填入,目前确定的极小值状态为 $s$ (状态压缩)
$f_{i, s} = \sum f_{i - 1, s’}$
$s’$ 为从 $s$ 中取出 $i$ 后能达到的状态。
由于这里 $s = s’$ 状态很多,所以预处理出 $num_s$ 表示填数后无法使 $s$ 改变的位置的个数。
$\LARGE{代码}$
代码比较难写
#include <bits/stdc++.h>
using namespace std;
const int N = 10, P = 12345678;
int n, m, ans;
int a[N][N], x[N], y[N];
int f[N * N][1 << N], num[1 << N];
bool used[N][N];
void add(int &x, int y) {
x = ((x + y) % P + P) % P;
}
bool check(int x, int y) {
for (int dx = -1; dx <= 1; dx ++ )
for (int dy = -1; dy <= 1; dy ++ )
if ((dx != 0 || dy != 0) && a[x + dx][y + dy])
return 1;
return 0;
}
int dp() {
memset(f, 0, sizeof f);
memset(num, 0, sizeof num);
int t = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[i][j])
x[t] = i, y[t ++ ] = j;
for (int i = 0; i < 1 << t; i ++ ) {
memset(used, 0, sizeof used);
for (int j = 0; j < t; j ++ )
if (!(i >> j & 1))
for (int dx = -1; dx <= 1; dx ++ )
for (int dy = -1; dy <= 1; dy ++ )
used[x[j] + dx][y[j] + dy] = true;
for (int j = 1; j <= n; j ++ )
for (int k = 1; k <= m; k ++ )
if (used[j][k] == 0)
num[i] ++ ;
}
f[0][0] = 1;
for (int i = 1; i <= n * m; i ++ ) {
for (int j = 0; j < 1 << t; j ++ ) {
add(f[i][j], 1ll * f[i - 1][j] * max(num[j] - i + 1, 0) % P);
for (int k = 0; k < t; k ++ )
if (!(j >> k & 1))
add(f[i][j | (1 << k)], f[i - 1][j]);
}
}
return f[n * m][(1 << t) - 1];
}
void dfs(int x, int y, int f) {
if (x == n + 1) return add(ans, f * dp()), void();
else if (y == m + 1) dfs(x + 1, 1, f);
else {
dfs(x, y + 1, f);
if (a[x][y] == 0 && !check(x, y)) {
a[x][y] = 1;
dfs(x, y + 1, -f);
a[x][y] = 0;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
char c;
cin >> c;
if (c == 'X') a[i][j] = 1;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (a[i][j] && check(i, j)) {
puts("0");
return 0;
}
dfs(1, 1, 1);
printf("%d", ans);
return 0;
}