比赛 20130923 评测结果 MEMMMMMMMM
题目名称 邮递员 最终得分 0
用户昵称 mikumikumi 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-10-12 21:32:10
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=10,SIZEM=20;
typedef long long LL;
int N,M;//N是列
LL f[SIZEM][SIZEN][1148576]={0};
class poi
{
public:
	int s[SIZEN];//0-无,1-左,2-右
	int x,y,k;
	poi(){}
	int val()//状态码
	{
		int ans=0;
		for(int i=1;i<=N;i++)
		{
			ans<<=2;
			ans+=s[i];
		}
		ans<<=2;ans+=k;
		return ans;
	}
	void clear()
	{
		x=y=k=0;
		memset(s,0,sizeof(s));
	}
	bool change(int U,int D,int L,int R)
	{
		if(U&&x==1) return 0;
		if(L&&y==1) return 0;
		if(R&&y==N) return 0;
		if(D&&x==M) return 0;
		if(L!=k) return 0;
		if(U!=s[y]) return 0;
		s[y]=D;
		k=R;
		y++;
		return 1;
	}
	void print()
	{
		cout<<x<<" "<<y<<" "<<k<<endl;
		for(int i=1;i<=N;i++) cout<<s[i]<<" ";
		cout<<endl;
		cout<<endl;
	}
};
void read()
{
	scanf("%d%d",&N,&M);
}
LL DP(poi S)
{
	if(f[S.x][S.y][S.val()]) return f[S.x][S.y][S.val()];
	if(S.y>N)
	{
		S.y=1;S.k=0;
		S.x++;
	}
	if(S.x>M) return 1;
	poi T;
	LL ans=0;
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=2;j++)
		{
			if(i==j) continue;
			T=S;if(T.change(i,j,0,0)) ans+=DP(T);
			T=S;if(T.change(i,0,j,0)) ans+=DP(T);
			T=S;if(T.change(i,0,0,j)) ans+=DP(T);
			T=S;if(T.change(0,i,j,0)) ans+=DP(T);
			T=S;if(T.change(0,i,0,j)) ans+=DP(T);
			T=S;if(T.change(0,0,i,j)) ans+=DP(T);
		}
	}
	//cout<<ans<<endl;
	//S.print();
	f[S.x][S.y][S.val()]=ans;
	return ans;
}
int main()
{
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	read();
	poi S;
	S.clear();
	S.x=1;S.y=1;
	LL ans=DP(S);
	printf("%I64d",ans);
	return 0;
}