题解：
和前两题差不多
只不过变成了有些一定走，有些不一定
代码：
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int HASH=10007; const int STATE=100010; int N,M,code[15],maze[15][15],ch[15],isend; struct HASHMAP { int head[HASH],next[STATE],size; ll state[STATE],f[STATE]; void init() { size=0; memset(head,-1,sizeof(head)); } void push(ll st,ll ans) { int h=st%HASH; for (int i=head[h];i!=-1;i=next[i]) if (state[i]==st) { f[i]+=ans; return; } state[size]=st; f[size]=ans; next[size]=head[h]; head[h]=size++; } }hm[2]; void decode(int *code,int m,ll st) { for (int i=m;i>=0;i--) { code[i]=st&7; st>>=3; } isend=st&1; } ll encode(int *code,int m) { int cnt=1; memset(ch,-1,sizeof(ch)); ch[0]=0; ll st=isend; for (int i=0;i<=m;i++) { if (ch[code[i]]==-1)ch[code[i]]=cnt++; code[i]=ch[code[i]]; st<<=3; st|=code[i]; } return st; } void shift(int *code,int m) { for (int i=m;i>0;i--)code[i]=code[i-1]; code[0]=0; } void dpblank(int i,int j,int cur) { int left,up; for (int k=0;k<hm[cur].size;k++) { decode(code,M,hm[cur].state[k]); left=code[j-1]; up=code[j]; if (isend) { if (left||up||maze[i][j]==2)continue; code[j-1]=code[j]=0; if (j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); continue; } if (left&&up) { if (left==up) { code[j-1]=code[j]=0; isend=1; if(j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } else { code[j-1]=code[j]=0; for (int t=0;t<=M;t++) if (code[t]==up)code[t]=left; if (j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } else if ((left&&(!up))||((!left)&&up)) { int t; if (left)t=left; else t=up; if (maze[i][j+1]) { code[j-1]=0; code[j]=t; hm[cur^1].push(encode(code,M),hm[cur].f[k]); } if (maze[i+1][j]) { code[j-1]=t; code[j]=0; if (j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } else { if (maze[i][j+1]&&maze[i+1][j]) { code[j-1]=code[j]=13; hm[cur^1].push(encode(code,M),hm[cur].f[k]); } if (maze[i][j]==1) { code[j-1]=code[j]=0; if (j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } } } void dpblock(int i,int j,int cur) { for (int k=0;k<hm[cur].size;k++) { decode(code,M,hm[cur].state[k]); code[j-1]=code[j]=0; if (j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } char str[20]; void init() { scanf("%d%d",&N,&M); memset(maze,0,sizeof(maze)); for (int i=1;i<=N;i++) { scanf("%s",&str); for (int j=1;j<=M;j++) { if (str[j-1]=='*')maze[i][j]=1; else if (str[j-1]=='O')maze[i][j]=2; } } } void solve() { int cur=0; hm[cur].init(); hm[cur].push(0,1); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) { hm[cur^1].init(); if(maze[i][j])dpblank(i,j,cur); else dpblock(i,j,cur); cur^=1; } ll ans=0; for (int i=0;i<hm[cur].size;i++)ans+=hm[cur].f[i]; printf("%I64d ",ans); } int main() { int T,iCase=0; scanf("%d",&T); while (T--) { iCase++; printf("Case %d: ",iCase); init(); solve(); } return 0; }