Accepted/7888K/313MS

poj1739.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
char MAP[10][10];
int dp[9][11][20010];
int power[]={1,3,9,27,81,243,729,2187,6561,19683,89049,177147,531441};
int main()
{
	int r,c,k,s,sk,m1,m2,ans,t;
	int std[10],stack;
	while (~scanf("%d%d",&r,&c) && r && c)
	{
		for (int i=0;i<r;i++)
			scanf("%s",MAP[i]);
		if (r==1)
		{
			ans=1;
			for (int i=0;i<c;i++)
			{
				if (MAP[0][i]=='#')
				{
					ans=0;
					break;
				}
			}
			printf("%d\n",ans);
			continue;
		}else if (c==1)
		{
			printf("%d\n",1);
			continue;
		}
		memset(dp,0,sizeof(dp));
		dp[0][0][0]=1;
		for (int i=0;i<r;i++)
		{
			for (int j=0;j<=c;j++)
			{
				if (i==r-1 && j==c)
					break;
				for (int s=0;s<power[c+1];s++)
				{
					if (dp[i][j][s]==0)
						continue;
					if (j==c)
					{
						if (s/power[c]==0)
							dp[i+1][0][s*3]+=dp[i][j][s];
					}else
					{
						m1=(s/power[j])%3;
						m2=(s/power[j+1])%3;
						if (MAP[i][j]=='#')
						{
							if (m1==0 && m2==0)
								dp[i][j+1][s]+=dp[i][j][s];
						}else
						{
							if (m1==0 && m2==0)
							{
								sk=s+power[j]+2*power[j+1];
								dp[i][j+1][sk]+=dp[i][j][s];
							}else if ((m1==0 && m2==1)||(m1==1 && m2==0))
							{
								t=s-m1*power[j]-m2*power[j+1];
								sk=t+power[j];
								dp[i][j+1][sk]+=dp[i][j][s];
								sk=t+power[j+1];
								dp[i][j+1][sk]+=dp[i][j][s];
							}else if ((m1==0 && m2==2)||(m1==2 && m2==0))
							{
								t=s-m1*power[j]-m2*power[j+1];
								sk=t+2*power[j];
								dp[i][j+1][sk]+=dp[i][j][s];
								sk=t+2*power[j+1];
								dp[i][j+1][sk]+=dp[i][j][s];
							}else if (m1==1 && m2==2)
								continue;
							else if (m1==2 && m2==1)
							{
								sk=s-m1*power[j]-m2*power[j+1];
								dp[i][j+1][sk]+=dp[i][j][s];
							}else if (m1==1 && m2==1)
							{
								for (k=j+2,stack=0;k<=c;k++)
								{
									t=(s/power[k])%3;
									if (t==1)
										stack++;
									else if (t==2)
									{
										if (stack==0)
											break;
										else
											stack--;
									}
								}
								if (k==c+1)
									continue;
								t=s-m1*power[j]-m2*power[j+1]-power[k];
								dp[i][j+1][t]+=dp[i][j][s];
							}else if (m1==2 && m2==2)
							{
								for (k=j-1,stack=0;k>=0;k--)
								{
									t=(s/power[k])%3;
									if (t==2)
										stack++;
									else if (t==1)
									{
										if (stack==0)
											break;
										else
											stack--;
									}
								}
								if (k==-1)
									continue;
								t=s-m1*power[j]-m2*power[j+1]+power[k];
								dp[i][j+1][t]+=dp[i][j][s];
							}
						}
					}
				}
			}
		}
		printf("%d\n",dp[r-1][c][1+2*power[c]]);
	}
	return 0;
}