- #include<stdio.h>
- #include<string.h>
- const int th[]={1,3,9,27,81,243,729,2187,6561,19683};
- bool v[15][15];
- int dp[15][15][20025];
- int plugleft,plugup;
- int checkbyte_three(int source,int place)
- {
- return (source/th[place])%3;
- }
- int main()
- {
- int N,M;
- while (scanf("%d%d",&N,&M)!=EOF)
- {
- if (N+M==0) return 0;
- memset(dp,0,sizeof(dp));
- memset(v,false,sizeof(v));
- for (int i=0;i<N;i++)
- {
- getchar();
- for (int j=0;j<M;j++)
- {
- char ch=getchar();
- if (ch=='#') v[i][j]=true;
- }
- }
- dp[0][0][0]=1;
- for (int i=0;i<N;i++)
- for (int j=0;j<=M;j++)
- {
- if (i==N-1 && j==M) break;
- else
- for (int s=0;s<=th[M+1];s++)
- if (dp[i][j][s]>0)
- {
- if (j==M)
- {
- if (s/th[M]==0) dp[i+1][0][s*3]+=dp[i][j][s];
- continue;
- }
- plugleft=checkbyte_three(s,j);
- plugup=checkbyte_three(s,j+1);
- if (v[i][j])
- {
- if (plugleft==0 && plugup==0) dp[i][j+1][s]+=dp[i][j][s];
- continue;
- }
- if (plugleft==0 && plugup==0)
- {
- int trans=s+th[j]+th[j+1]*2;
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- if ((plugleft==1 && plugup==0) || (plugleft==0 && plugup==1))
- {
- int tmp=s-plugleft*th[j]-plugup*th[j+1];
- int trans=tmp+th[j];
- dp[i][j+1][trans]+=dp[i][j][s];
- trans=tmp+th[j+1];
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- if ((plugleft==2 && plugup==0) || (plugleft==0 && plugup==2))
- {
- int tmp=s-plugleft*th[j]-plugup*th[j+1];
- int trans=tmp+th[j]*2;
- dp[i][j+1][trans]+=dp[i][j][s];
- trans=tmp+th[j+1]*2;
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- if (plugleft==1 && plugup==1)
- {
- int sum=0,mat=M+1;
- for (int k=j+1;k<=M;k++)
- {
- int dig=checkbyte_three(s,k);
- if (dig==1) sum++;
- if (dig==2) sum--;
- if (sum==0)
- {
- mat=k;
- break;
- }
- }
- if (mat==M+1) continue;
- int trans=s-th[j]-th[j+1]-th[mat];
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- if (plugleft==2 && plugup==2)
- {
- int sum=0,mat=-1;
- for (int k=j;k>=0;k--)
- {
- int dig=checkbyte_three(s,k);
- if (dig==1) sum--;
- if (dig==2) sum++;
- if (sum==0)
- {
- mat=k;
- break;
- }
- }
- if (mat==-1) continue;
- int trans=s-th[j]*2-th[j+1]*2+th[mat];
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- if (plugleft==1 && plugup==2) continue;
- if (plugleft==2 && plugup==1)
- {
- int trans=s-th[j]*2-th[j+1];
- dp[i][j+1][trans]+=dp[i][j][s];
- }
- }
- }
- printf("%d\\n",dp[N-1][M][1+2*th[M]]);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137472.html
来源: http://www.codesnippet.cn/detail/251120137472.html