Description:

用 $L$ 形的地板铺满 $N\times M$ 的网格中空白区域的方案数。

$N\times M\le 100$

Solution:

插头 $DP$ ， $0$ 表示没有插头， $1$ 表示有一个还没转弯的插头， $2$ 表示有一个已经转弯的插头。转移时可以新增一个 $1$ 插头，新建两个 $2$ 插头，顺延 $1$ 、 $2$ 插头， $1$ 插头转向成 $2$ 插头，合并两个 $1$ 插头。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m;

#define MAXL 110

#define MOD 20110520

bool map[MAXL][MAXL];

inline bool getc()

{

	char c = getchar();

	while(c != '_' && c != '*')c = getchar();

	if(c == '_')return true;

	else return false;

}

inline void init()

{

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

	if(n >= m)for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)map[i][j] = getc();

	else{for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)map[j][i] = getc();;swap(n,m);}

	return;

}

#define HASH 300007

#define STATE 3000000

struct hash_map

{

	int lin[HASH],nxt[STATE],siz;

	ll dat[STATE],f[STATE];

	void init(){siz = 0;memset(lin,0,sizeof(lin));}

	void add(ll sta,ll ans)

	{

		int hsh = sta % HASH;

		for(register int i = lin[hsh];i != 0;i = nxt[i])if(dat[i] == sta){f[i] = (f[i] + ans) % MOD;return;}

		++siz;dat[siz] = sta;f[siz] = ans;nxt[siz] = lin[hsh];lin[hsh] = siz;return;

	}

}h[2];

int code[MAXL],code_[MAXL];

inline void shift(int *code,int *code_,bool tag)

{

	if(tag){for(register int i = m;i > 0;--i)code_[i] = code[i - 1];code_[0] = 0;}

	else{for(register int i = m;i >= 0;--i)code_[i] = code[i];}

	return;

}

inline void decode(int *code,int m,ll sta)

{

	for(register int i = m;i >= 0;--i)

	{

		code[i] = sta & 3;

		sta = sta >> 2;

	}

	return;

}

inline ll encode(int *code,int m)

{

	ll sta = 0;

	for(register int i = 0;i <= m;++i)

	{

		sta = sta << 2;

		sta |= code[i];

	}

	return sta;

}

inline void dp(int i,int j,int cur)

{

	bool flag = (j == m);

	int left,up;

	for(register int k = 1;k <= h[cur].siz;++k)

	{

		decode(code,m,h[cur].dat[k]);

		left = code[j - 1];up = code[j];

		if(!map[i][j]){

			if(left == 0 && up == 0)

			{

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

		}

		else{

			if(left == 0 && up == 0){

				if(i < n)

				{

					code[j - 1] = 1;code[j] = 0;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				if(j < m)

				{

					code[j - 1] = 0;code[j] = 1;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				if(i < n && j < m)

				{

					code[j - 1] = 2;code[j] = 2;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

			}

			if(left == 0 && up == 1){

				if(i < n)

				{

					code[j - 1] = 1;code[j] = 0;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				if(j < m)

				{

					code[j - 1] = 0;code[j] = 2;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

			}

			if(left == 0 && up == 2){

				if(i < n)

				{

					code[j - 1] = 2;code[j] = 0;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

			if(left == 1 && up == 0){

				if(i < n)

				{

					code[j - 1] = 2;code[j] = 0;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				if(j < m)

				{

					code[j - 1] = 0;code[j] = 1;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

			}

			if(left == 1 && up == 1){

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

			if(left == 2 && up == 0){

				if(j < m)

				{

					code[j - 1] = 0;code[j] = 2;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

		}

	}

	return;

}

void solve()

{

	int cur = 0;

	h[cur].init();

	h[cur].add(0,1);

	for(register int i = 1;i <= n;++i)

	{

		for(register int j = 1;j <= m;++j)

		{

			h[cur ^ 1].init();

			dp(i,j,cur);

			cur ^= 1;

		}

	}

	bool found = false;

	for(register int i = h[cur].lin[0];i != 0;i = h[cur].nxt[i])

	{

		if(h[cur].dat[i] == 0)

		{

			found = true;

			printf("%lld\n",h[cur].f[i]);

		}

	}

	if(!found)

	{

		puts("0");

	}

	return;

}

int main()

{

	init();

	solve();

	return 0;

}