感谢大佬的教导->这里
容易注意到，本题的合法路径“L型地板”有一些特殊的地方：拐弯且仅拐弯一次。
这由于一条路径只有两种状态：拐弯过和没拐弯过，因此我们可以尝试着这样定义新的插头：
我们使用三进制，0代表没有插头，1代表没拐弯过的路径，2代表已经拐弯过的路径。
依然设当前转移到格子(x,y)，设y-1号插头状态为p1，y号插头状态为p2。
那么会有下面的几种情况：
情况1：p1==0&&p2==0
这时我们有三种可选的策略：
①以当前位置为起点，从p1方向引出一条新的路径（把p1修改为1号插头）
②以当前位置为起点，从p2方向引出一条新的路径（把p2修改为1号插头）
③以当前位置为“L”型路径的转折点，向p1，p2两个方向均引出一个2号插头.
情况2：p1==0&&p2==1
由于p2节点还没有拐过弯，因此我们有2种可选的策略：
①继续直走，不拐弯，即上->下（把p1修改为1号插头，p2置0）
②选择拐弯，即上->右（把p2改为2号插头）
情况3：p1==1&&p2==0
这种情况和情况2类似
情况4：p1==0&&p2==2
由于p2节点已经拐过弯，所以我们有如下的两种策略：
①路径在此停止。那么我们以本格作为L型路径的一个端点。如果当前处于最后一个非障碍格子，如果没有其他的插头，我们此时就可以统计答案了。
②路径延续。由于p2已经转弯过，因此我们只能选择继续直走，即上->下（把p1修改为2号插头，p2置0）和之前相似的方法把独立插头传递下去即可。
情况5：p1==2&&p2==0
这种情况与情况4类似
情况6：p1==1&&p2==1
这种情况下，两块地板均没有拐过弯，因此我们可以在本格将这两块地板合并，形成一个合法的“L”型路径，并将本格看做他们的转折点。（把p1和p2都置为0）
至此，新插头定义的状态转移已经讨论完成。
不难发现，这种新的插头定义可以处理可能发生的所有可行情况。
然后上代码
1 //minamoto 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=105,HASH=200097,mod=20110520; 7 int ans,n,m,lastx,lasty;char c[N][N];bool room[N][N]; 8 struct node{ 9 int val[HASH],key[HASH],Hash[HASH],sz; 10 inline void init(){ 11 memset(val,0,sizeof(val)),memset(Hash,0,sizeof(Hash)); 12 memset(key,-1,sizeof(key)),sz=0; 13 } 14 inline void newhash(int id,int state){Hash[id]=++sz,key[sz]=state;} 15 inline int &operator [](const int state){ 16 for(int i=state%HASH;;i=(i+1==HASH)?0:i+1){ 17 if(!Hash[i]) newhash(i,state); 18 if(key[Hash[i]]==state) return val[Hash[i]]; 19 } 20 } 21 }f[2]; 22 inline int find(int state,int pos){return (state>>((pos-1)<<1))&3;} 23 inline void set(int &state,int pos,int val){ 24 pos=(pos-1)<<1,state|=3<<pos,state^=3<<pos,state^=val<<pos; 25 } 26 void solve(int x,int y){ 27 int now=((x-1)*m+y)&1,last=now^1,tot=f[last].sz; 28 f[now].init(); 29 for(int i=1;i<=tot;++i){ 30 int state=f[last].key[i],val=f[last].val[i]; 31 int plug1=find(state,y),plug2=find(state,y+1); 32 if(!room[x][y]){ 33 if(!plug1&&!plug2) (f[now][state]+=val)%=mod; 34 } 35 else{ 36 if(!plug1&&!plug2){ 37 if(room[x+1][y]) set(state,y,1),set(state,y+1,0),(f[now][state]+=val)%=mod; 38 if(room[x][y+1]) set(state,y,0),set(state,y+1,1),(f[now][state]+=val)%=mod; 39 if(room[x][y+1]&&room[x+1][y]) set(state,y,2),set(state,y+1,2),(f[now][state]+=val)%=mod; 40 } 41 else if(!plug1&&plug2){ 42 if(plug2==1){ 43 if(room[x+1][y]) set(state,y,1),set(state,y+1,0),(f[now][state]+=val)%=mod; 44 if(room[x][y+1]) set(state,y,0),set(state,y+1,2),(f[now][state]+=val)%=mod; 45 } 46 else{ 47 set(state,y,0),set(state,y+1,0),(f[now][state]+=val)%=mod; 48 if(x==lastx&&y==lasty&&!state) (ans+=val)%=mod; 49 if(room[x+1][y]) set(state,y,2),set(state,y+1,0),(f[now][state]+=val)%=mod; 50 } 51 } 52 else if(plug1&&!plug2){ 53 if(plug1==1){ 54 if(room[x][y+1]) set(state,y,0),set(state,y+1,1),(f[now][state]+=val)%=mod; 55 if(room[x+1][y]) set(state,y,2),set(state,y+1,0),(f[now][state]+=val)%=mod; 56 } 57 else{ 58 set(state,y,0),set(state,y+1,0),(f[now][state]+=val)%=mod; 59 if(x==lastx&&y==lasty&&!state) (ans+=val)%=mod; 60 if(room[x][y+1]) set(state,y,0),set(state,y+1,2),(f[now][state]+=val)%=mod; 61 } 62 } 63 else if(plug1==1&&plug2==1){ 64 set(state,y,0),set(state,y+1,0),(f[now][state]+=val)%=mod; 65 if(x==lastx&&y==lasty&&!state)(ans+=val)%=mod; 66 } 67 } 68 } 69 } 70 int main(){ 71 // freopen("testdata.in","r",stdin); 72 scanf("%d%d",&n,&m); 73 for(int i=1;i<=n;++i) scanf("%s",c[i]+1); 74 for(int i=1;i<=n;++i) 75 for(int j=1;j<=m;++j) 76 room[i][j]=(c[i][j]=='_'); 77 if(m>n){ 78 for(int i=1;i<=n;++i) 79 for(int j=i+1;j<=m;++j) 80 swap(room[i][j],room[j][i]); 81 swap(n,m); 82 } 83 int flag=1; 84 for(int i=n;i&&flag;--i) 85 for(int j=m;j&&flag;--j) 86 if(room[i][j]){lastx=i,lasty=j;flag=0;} 87 f[0].init(),f[0][0]=1; 88 for(int i=1;i<=n;++i){ 89 for(int j=1;j<=m;++j) solve(i,j); 90 if(i!=n) 91 for(int j=1,last=(i*m)&1,tot=f[last].sz;j<=tot;++j) 92 f[last].key[j]<<=2; 93 } 94 printf("%d ",ans); 95 return 0; 96 }