【CF845F】Guards In The Storehouse 插头DP

【CF845F】Guards In The Storehouse

题意：一个n*m的房间，每个格子要么是障碍要么是空地。对于每个空地你可以选择放或者不放守卫。一个守卫能保护到的位置是：他右面的一行空地+下面的一列空地，但是不能穿过障碍（可以穿过另一个守卫）。现在要求至多有1个空地没有被保护，求放置守卫的方案数。

$n\times m\le 250$

题解：n和m中较小者不超过15，所以插头DP不解释~

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int P=1000000007;

int f[2][(1<<16)+1][2];

int n,m,msk,ans;

char str[255][255];

inline void upd(int &x,int y) {x+=y;	if(x>=P)	x-=P;}

int main()

{

	scanf("%d%d",&n,&m);

	int i,j,d=0,S,T,p,q,x,y,v0,v1;

	for(i=0;i<n;i++)	scanf("%s",str[i]);

	if(n<m)

	{

		for(i=0;i<n;i++)	for(j=i;j<m;j++)	swap(str[i][j],str[j][i]);

		swap(n,m);

	}

	msk=(1<<(m+1))-1,f[0][0][0]=1;

	for(i=0;i<n;i++)

	{

		for(j=0;j<m;j++)

		{

			d^=1,memset(f[d],0,sizeof(f[d]));

			for(S=0;S<=msk;S++)

			{

				x=j,y=j+1,p=(S>>x)&1,q=(S>>y)&1,T=S^(p<<x)^(q<<y),v0=f[d^1][S][0],v1=f[d^1][S][1];

				if(!v0&&!v1)	continue;

				if(str[i][j]=='x')

				{

					upd(f[d][T][0],v0),upd(f[d][T][1],v1);

					continue;

				}

				upd(f[d][T|(1<<x)|(1<<y)][0],v0),upd(f[d][T|(1<<x)|(1<<y)][1],v1);

				if(p||q)	upd(f[d][T|(q<<x)|(p<<y)][0],v0),upd(f[d][T|(q<<x)|(p<<y)][1],v1);

				else	upd(f[d][T][1],v0);

			}

		}

		d^=1,memset(f[d],0,sizeof(f[d]));

		for(S=0;S<=msk;S++)	upd(f[d][(S<<1)&msk][0],f[d^1][S][0]),upd(f[d][(S<<1)&msk][1],f[d^1][S][1]);

	}

	for(S=0;S<=msk;S++)	upd(ans,f[d][S][0]),upd(ans,f[d][S][1]);

	printf("%d",ans);

	return 0;

}//1 4  ....