本文共 4093 字，大约阅读时间需要 13 分钟。
题意 有一个 n×m 的矩阵，其中每个数都是 [1,n×m] 中的一个，不会重复。有一些地方的值比周围的8个位置都小（如果有的话）。给出这些位置，求这样的矩阵有多少个。 n≤4,m≤7 。
/*状态压缩好题。对于局部最小值的位置一定不会超过8个，对于这种情况可以直接状态压缩，用最多8个二进制1来表示那些位置已经放了数。 由于有些位置不受任何限制，所以将那些不受限制的点变成局部最小值位置，那么当这些点被确定后，剩下的位置一定是等价的。由于只能将给定的位置作为局部最小值位置，所以要减去，此处用容斥原理（奇加偶减）。 */#include #include #include #include #include #define ll long long#define inf 1e9#define eps 1e-10#define md 12345678#define N 1010using namespace std;bool mp[6][9],ok[6][9];int cnt[N];ll f[1010][100];int n,m,mxn; ll ans=0; char st[110];struct point { int x,y;} q[100];int lx[8]={1,0,-1,0,1,1,-1,-1},ly[8]={0,1,0,-1,1,-1,1,-1};ll solve()//求 { int tot=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (mp[i][j]) q[tot++]=(point){i,j}; for (int S=0;S<(1< n||y>m) continue; ok[x][y]=1; } } else cnt[S]++; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if ((!ok[i][j]&&(!mp[i][j]))) cnt[S]++;//既不是局部最小值位置，也不会被局部最小值限制（随意选择） } memset(f,0,sizeof(f)); f[0][0]=1; for (int i=0;i<=mxn;i++) { for (int S=0;S<(1< 0) f[S][i]=(f[S][i]+f[S][i-1]*(cnt[S]-(i-1))%md)%md; if (f[S][i]==0) continue; for (int j=0;j mxn) { ll x=solve(); if (s&1) ans=(ans-x+md)%md; else ans=(ans+x)%md; return; } dfs(mxn+1,s); for (int now=dep;now<=mxn;now++) { int i=(now-1)/m+1,j=(now-1)%m+1; if (!mp[i][j]) { bool ok=1; for (int k=0;k<=7;k++) { int x=i+lx[k],y=j+ly[k]; if (x<1||y<1||x>n||y>m) continue; if (mp[x][y]) { ok=0; break;} } if (ok)//将不受限制的位置当做局部最小值。 { mp[i][j]=1; dfs(now+1,s+1); mp[i][j]=0; } } }}void check(){ for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (mp[i][j]) { for (int k=0;k<=7;k++) { int x=i+lx[k],y=j+ly[k]; if (mp[x][y]) { printf("0\n"); exit(0); } } } }}int main(){ scanf("%d%d",&n,&m); mxn=n*m; for (int i=1;i<=n;i++) { scanf("%s",st+1); for (int j=1;j<=m;j++) mp[i][j]=st[j]=='X'; } check(); dfs(1,0); printf("%d\n",ans); return 0;}#include #include #include using namespace std;const int MAXN = 10, MAXM = 300;const int Mo = 12345678;int fx[8][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 1}, {1, -1}, {1, 1}, {-1, -1}};struct Coor { int x, y;} Ex[MAXN * MAXN];char S[MAXN][MAXN];int Ord, N, M, Num, Rest[MAXM], Ans, F[MAXN * MAXN][MAXM];bool NoAns() { for (int i = 1; i <= N; i ++) for (int j = 1; j <= M; j ++) { if (S[i][j] == '.') continue; for (int k = 0; k < 8; k ++) if (S[i + fx[k][0]][j + fx[k][1]] == 'X') return 1; } return 0;}void Prepare() { Num = 0; for (int i = 1; i <= N; i ++) for (int j = 1; j <= M; j ++) if (S[i][j] == 'X') Ex[++ Num].x = i, Ex[Num].y = j; for (int i = 0; i < (1 << Num); i ++) { Rest[i] = 0; for (int j = 1; j <= Num; j ++) S[Ex[j].x][Ex[j].y] = (i & (1 << (j - 1))) ? '.' : 'X'; for (int x = 1; x <= N; x ++) for (int y = 1; y <= M; y ++) { if (S[x][y] == 'X') continue; bool Flag = 1; for (int k = 0; k < 8; k ++) if (S[x + fx[k][0]][y + fx[k][1]] == 'X') { Flag = 0; break; } if (Flag) Rest[i] ++; } } for (int i = 1; i <= Num; i ++) S[Ex[i].x][Ex[i].y] = 'X';}int Get() { Prepare(); F[0][0] = 1; for (int i = 1; i <= N * M; i ++) for (int j = 0; j < (1 << Num); j ++) { F[i][j] = 1ll * F[i - 1][j] * (Rest[j] - i + 1) % Mo; for (int k = 1; k <= Num; k ++) if (j & (1 << (k - 1))) F[i][j] = (F[i][j] + F[i - 1][j - (1 << (k - 1))]) % Mo; } return F[N * M][(1 << Num) - 1];}void Dfs(int x, int y, int Cnt) { if (x > N) { int Val = ((Ord & 1) == (Cnt & 1)) ? 1 : -1; Ans = ((Ans + Val * Get()) % Mo + Mo) % Mo; return; } int xx = x, yy = y + 1; if (yy > M) xx ++, yy = 1; if (S[x][y] == 'X') Dfs(xx, yy, Cnt + 1); else { Dfs(xx, yy, Cnt); for (int k = 0; k < 8; k ++) if (S[x + fx[k][0]][y + fx[k][1]] == 'X') return; S[x][y] = 'X'; Dfs(xx, yy, Cnt + 1); S[x][y] = '.'; }}void Solve() { Dfs(1, 1, 0); printf("%d\n", Ans);}void Work() { memset(S, 0, sizeof S); Ord = Ans = 0; scanf("%d%d", &N, &M); for (int i = 1; i <= N; i ++) { scanf("%s", S[i] + 1); for (int j = 1; j <= M; j ++) if (S[i][j] == 'X') Ord ++; } if (NoAns()) { printf("0\n"); return; } Solve();}int main() {// freopen("garden.in", "r", stdin), freopen("garden.out", "w", stdout); int Test; scanf("%d\n", &Test); for (int i = 1; i <= Test; i ++) Work();}
转载地址：http://yrqji.baihongyu.com/