bzoj 2331: [SCOI2011]地板 — 插头dp

2331: [SCOI2011]地板

Time Limit: 5 Sec  Memory Limit: 128 MB

Description

lxhgww的小名叫“小L”，这是因为他总是很喜欢L型的东西。小L家的客厅是一个的矩形，现在他想用L型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。现在小L想知道，用L型的地板铺满整个客厅有多少种不同的方案？

需要注意的是，如下图所示，L型地板的两端长度可以任意变化，但不能长度为0。铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。

Input

输入的第一行包含两个整数，R和C，表示客厅的大小。

接着是R行，每行C个字符。’_’表示对应的位置是空的，必须铺地板；’*’表示对应的位置有柱子，不能铺地板。

Output

输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以20110520的余数。

Sample Input

2 2

*_

__

Sample Output

1

HINT

R*C<=100

入门第一题。。

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define P 20110520
#define M 200010
#define N 110
int n,m,ed,ans;
bool mp[N][N];
char s[N];
int f[2][M],v[2][M],a[N];
struct qaz{int x,z;};
queue<qaz>q;
inline int gx(int x,int a1,int a2)
{
	int sum=0;
	for(int i=m+1;i;i--)
		sum=sum*3+(i==x?a1:(i==x+1?a2:a[i]));
	return sum;
}
void up(int x,int z,int ta)
{
	if(x==ed)
	{
		(ans+=ta)%=P;
		return;
	}
	x++;
	int k=x&1;
	if(v[k][z]^x)
	{
		v[k][z]=x;f[k][z]=0;
		q.push((qaz){x,z});
	}
	(f[k][z]+=ta)%=P;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			if(n>m) mp[j][i]=(s[j]=='_');
			else mp[i][j]=(s[j]=='_');
	}
	if(n<m) swap(n,m);
	ed=n*m-1;
	while(!mp[ed%m+1][ed/m+1]) ed--;
	f[0][0]=v[0][0]=1;
	q.push((qaz){0,0});
	qaz p;
	int x,y,ta;
	while(!q.empty())
	{
		p=q.front();q.pop();
		ta=f[p.x&1][p.z];
		if(p.x%m==0) p.z*=3;
		x=p.x%m+1;y=p.x/m+1;
		memset(a,0,m+2<<2);
		for(int i=1,j=p.z;j;i++,j/=3) a[i]=j%3;
		if(!mp[x][y]) up(p.x,gx(100,0,0),ta);
		else if(a[x]==1&&a[x+1]==1) up(p.x,gx(x,0,0),ta);
		else if(!a[x]&&!a[x+1])
		{
			if(mp[x+1][y]) up(p.x,gx(x,0,1),ta);
			if(mp[x][y+1]) up(p.x,gx(x,1,0),ta);
			if(mp[x][y+1]&&mp[x+1][y]) up(p.x,gx(x,2,2),ta);
		}
		else if(!a[x])
		{
			if(mp[x][y+1]) up(p.x,gx(x,a[x+1],0),ta);
			if(mp[x+1][y]&&a[x+1]==1) up(p.x,gx(x,0,2),ta);
			if(a[x+1]==2) up(p.x,gx(x,0,0),ta);
		}
		else if(!a[x+1])
		{
			if(mp[x+1][y]) up(p.x,gx(x,0,a[x]),ta);
			if(mp[x][y+1]&&a[x]==1) up(p.x,gx(x,2,0),ta);
			if(a[x]==2) up(p.x,gx(x,0,0),ta);
		}
	}
	printf("%d\n",ans);
	return 0;
}