2411.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#define NMAX 15
#define DMAX 12
#define NMAX3 200000
#define NMAX2 3000
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int bit2[NMAX]={0},bit3[NMAX]={0};
__int64 m[NMAX][NMAX2]={0};
int b32[NMAX3][2]={0};
bool f[NMAX3]={0};
int b22[NMAX2]={0};
int h,w;
void initbit()
{
	bit2[1]=1;
	bit3[1]=1;
	int i;
	for(i=2;i<=NMAX;i++)
	{
		bit2[i]=bit2[i-1]*2;
		bit3[i]=bit3[i-1]*3;
	}
}
int c[NMAX];
void bit3toint(int t)
{
	int i;
	for(i=w;i>=1;i--)
	{
		c[i]=t%3;
		t/=3;
	}
}
int t[3][NMAX]={0};
int firstexist()
{
	memset(t,0,sizeof(t));
	int i;
	for(i=1;i<w;i++)
	{
		if(c[i]==0)
			continue;
		if(t[1][i])
			return 0;
		if(c[i]==1)
		{
			t[1][i]=1;
			t[1][i+1]=1;
		}
		else
			return 0;
	}
	if(c[i])
		return 0;
	return 1;
}
int exist()
{
	memset(t,0,sizeof(t));
	int i;
	for(i=1;i<w;i++)
	{
		if(c[i]==0)
			continue;
		if(t[1][i])
			return 0;
		if(c[i]==1)
		{
			t[1][i]=1;
			t[1][i+1]=1;
		}
		else
		{
			t[1][i]=1;
			t[2][i]=1;
		}
	}
	if(c[i]==0)
		return 1;
	if(t[1][i]==1)
		return 0;
	if(c[i]==1)
		return 0;
	if(c[i]==2)
	{
		t[1][i]=1;		
		t[2][i]=1;
	}
	return 1;
}
int firsttoint2()
{
	int i;
	int tmp=0;
	for(i=1;i<=w;i++)
	{
		tmp+=t[1][i]*bit2[w-i+1];
	}
	return tmp;
}
void toint2(int &a,int &b)
{
	int i;
	a=0;
	b=0;
	for(i=1;i<=w;i++)
	{
		a+=t[1][i]*bit2[w-i+1];
		b+=(!t[2][i])*bit2[w-i+1];
	}
}
int init()
{
	memset(m,0,sizeof(m));
	initbit();
	int i,j;
	for(i=0;i<bit3[w+1];i++)
	{
		bit3toint(i);
		if(firstexist()==0)
			continue;

		m[1][firsttoint2()]+=1;
	}
	memset(f,0,sizeof(f));
	memset(b32,0,sizeof(b32));
	for(j=0;j<bit3[w+1];j++)
	{
		bit3toint(j);
		if(exist()==0)
			continue;
		int a,b;
		f[j]=1;
		toint2(a,b);
		b32[j][0]=a;
		b32[j][1]=b;
	}
	for(i=2;i<=h;i++)
	{
		for(j=0;j<bit3[w+1];j++)
		{
			if(!f[j])
				continue;
			m[i][b32[j][0]]+=m[i-1][b32[j][1]];
		}
	}
	return 1;
}


int check()
{
	if(exist()==0)
		return 0;
	for(int i=w;i>=w-w+1;i--)
	{
		if(t[1][i]==0)
			return 0;
	}
	return 1;
}


void solve()
{
	__int64 ans=0;
/*	for(int i=0;i<bit3[w+1];i++)
	{
		bit3toint(i);
		if(check())
		{
			int p=firsttoint2();
			ans+=m[h][firsttoint2()];
		}
	}
*/	printf("%I64d\n",m[h][bit2[w+1]-1]);
}


main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	
	
	while(1)
	{
		scanf("%d%d",&h,&w);
		if(!h)
			break;
		if(h%2||w%2)
			if(!(h%2==0||w%2==0))
			{
				printf("0\n");
				continue;
			}
		init();
		solve();
	}

#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}