Description
lxhgww的小名叫“小L”，这是因为他总是很喜欢L型的东西。小L家的客厅是一个的矩形，现在他想用L型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。现在小L想知道，用L型的地板铺满整个客厅有多少种不同的方案？
需要注意的是，如下图所示，L型地板的两端长度可以任意变化，但不能长度为0。铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。
Input
输入的第一行包含两个整数，R和C，表示客厅的大小。
接着是R行，每行C个字符。’_’表示对应的位置是空的，必须铺地板；’*’表示对应的位置有柱子，不能铺地板。
Output
输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以20110520的余数。
Sample Input
2 2
*_
__
Sample Output
1
插头dp……蒟蒻的模板慢得要死……用0表示无插头，1表示有未拐的插头，2表示已拐的插头……
然后转移就自己YY一下就好了……
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=;
const int MAXN=;
int i;
struct na{
int x,z;
na(int xx,int zz):x(xx),z(zz){}
};
int n,m,x,y,z,a[],k,p1,p2,en,t;
bool map[][];
int f[][MAXN+],ans=;
int v[][MAXN+];
queue <na> q;
inline int gx(int x,int q1,int q2){k=;for (register int i=m+;i;i--) k=k*+(i==x?q1:(i==x+?q2:a[i]));return k;}
inline void up(int r,int z,int lj){
if (r==en){
ans+=lj;
if (ans>=INF) ans-=INF;
return;
}
r++;
k=r%;
if (v[k][z]!=r) v[k][z]=r,f[k][z]=,q.push(na(r,z));
f[k][z]+=lj;if (f[k][z]>=INF) f[k][z]-=INF;
}
char c[];
int main(){
register int i,j,p;
scanf("%d%d",&n,&m);
if (n<m){
swap(n,m);
for (j=;j<=m;j++){
scanf("%s",c);
for (i=;i<=n;i++)
map[j][i]=c[i-]=='_';
}
}else{
for (j=;j<=n;j++){
scanf("%s",c);
for (i=;i<=m;i++)
map[i][j]=c[i-]=='_';
}
}
en=n*m-;
while(!map[en%m+][en/m+]) en--;
f[][]=v[][]=;
q.push(na(,));
while(!q.empty()){
na no=q.front();q.pop();
int an=f[no.x%][no.z];
if(no.x%m==) no.z*=;
x=no.x%m+;y=no.x/m+;
for (i=;i<=m+;i++) a[i]=;
for (i=,j=no.z;j;i++,j/=) a[i]=j%;
if (!map[x][y]) up(no.x,gx(,,),an);else
if (a[x]==&&a[x+]==) up(no.x,gx(x,,),an);else
if (a[x]==&&a[x+]==){
if (map[x+][y]) up(no.x,gx(x,,),an);
if (map[x][y+]) up(no.x,gx(x,,),an);
if (map[x][y+]&&map[x+][y]) up(no.x,gx(x,,),an);
}else
if (a[x]==){
if (map[x][y+]) up(no.x,gx(x,a[x+],),an);
if (map[x+][y]&&a[x+]==) up(no.x,gx(x,,),an);
if (a[x+]==) up(no.x,gx(x,,),an);
}else
if (a[x+]==){
if (map[x+][y]) up(no.x,gx(x,,a[x]),an);
if (map[x][y+]&&a[x]==) up(no.x,gx(x,,),an);
if (a[x]==) up(no.x,gx(x,,),an);
}
}
printf("%d\n",ans);
}