欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ 2669

程序员文章站 2024-01-12 09:29:28
...
题意
有一个 n×m 的矩阵,其中每个数都是 [1,n×m] 中的一个,不会重复。有一些地方的值比周围的8个位置都小(如果有的话)。给出这些位置,求这样的矩阵有多少个。

n≤4,m≤7 。

/*
状态压缩好题。对于局部最小值的位置一定不会超过8个,对于这种情况可以直接状态压缩,用最多8个二进制1来表示那些位置已经放了数。 由于有些位置不受任何限制,所以
将那些不受限制的点变成局部最小值位置,那么当这些点被确定后,剩下的位置一定是等价的。由于只能将给定的位置作为局部最小值位置,所以要减去,此处用容斥原理
(奇加偶减)。 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1e9
#define eps 1e-10
#define md 12345678
#define N 1010
using 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<<tot);S++)//针对不同的状态S找cnt【s】 :随意选择的点的个数和局部最小值的个数的总和 
	{
		cnt[S]=0;
		memset(ok,0,sizeof(ok));
		for (int e=0;e<tot;e++)
		{
			if (!(S&(1<<e)))
			{
				int i=q[e].x,j=q[e].y;
				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;
					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<<tot);S++)
		{
			if (i&&(cnt[S]-(i-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<tot;j++)
			{
				if (!(S&(1<<j))) f[S|(1<<j)][i+1]=(f[S|(1<<j)][i+1]+f[S][i])%md;//从当前状态把扩展的状态累加。 
			}
		}
	}
	return f[(1<<tot)-1][mxn];
	/*这里再给出一种从当前状态从前一种状态扩展而来的写法
	for(int i=0;i<=mxn;i++)
	{
		for(int S=0;S<(1<<tot);S++)
		{
			f[S][i]=(f[S][i] +f[S][i-1]*(cnt[S]-(i-1))%md)%md;
			for(int j=1;j<=tot;j++)
			{
				if(!(S&(1<<(j-1)))) continue;
				f[S][i]=(f[S][i]+f[S^(1<<(j-1))][i-1])%md;
			 } 
		}
	}
	*/ 
}
void dfs(int dep,int s)
{
	if (dep>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 <cstring>
#include <cstdio>
#include <algorithm>

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();
}