记录编号	161282	评测结果	AAAAAAA
题目名称	漫游小镇	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-05-03 18:48:53	内存使用	0.70 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<string.h>
using namespace std;
typedef long long LL;
int n,maxn=100007;
int ans=0;
bool mp[10][10]={0};
class miku
{
public:
	int id,sum;
	miku() {}
	miku(int a,int b)
	{
		id=a,sum=b;
	}
};
deque<miku> f[2];
int h[100007];
LL get(LL id,int j)
{
	return (id>>((j-1)<<1))&3;
}
void check(LL s)
{
	for(int i=1;i<=n+1;i++) cout<<get(s,i)<<" ";
	cout<<endl;
}
void push(int k,LL id,LL sum)
{
	int now=id%maxn;
	while(h[now])
	{
		if(f[k][h[now]].id==id){
			f[k][h[now]].sum+=sum; return;
		}
		now++;
		if(now==maxn) now=0;
	}
	h[now]=f[k].size();
	f[k].push_back(miku(id,sum));
}
LL change(LL id,int k,int t)
{
	int temp=(k-1)<<1;
	id&=~(3<<temp);
	return id|(t<<temp);
}
LL find(LL id,int k,int now)
{
	int dat=now,temp;
	while(k>=1&&k<=n+1)
	{
		k+=now;
		temp=get(id,k);
		if(temp==1) dat++;
		if(temp==2) dat--;
		if(dat==0) return k;
	}
	cout<<"fuck1"<<endl;
	return -1;
}
void solve()
{
	int k=0;
	LL temp;
	f[k].push_back(miku(0,1));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			k^=1;
			f[k].clear();
			memset(h,0,sizeof(h));
			for(int km=0;km<f[k^1].size();km++)
			{
			LL s=f[k^1][km].id,date=f[k^1][km].sum;	
				int p=get(s,j),q=get(s,j+1);
				//check(s);
				//cout<<i<<" "<<j<<" "<<date<<endl;
				if(p==0&&q==0)
				{
					if(i==1&&j==1)
					{//填加独立插头
					if(mp[i+1][j]){temp=change(s,j,3);push(k,temp,date);}
					if(mp[i][j+1]){temp=change(s,j+1,3);push(k,temp,date);}
					}
					else if(mp[i+1][j]&&mp[i][j+1])
					{
						temp=change(s,j,1);temp=change(temp,j+1,2);
						push(k,temp,date);
					}
					else if(i==n&&j==1)
					{
						//cout<<"fuck"<<endl;
						temp=change(s,j+1,3);
						push(k,temp,date);
					}
				}
				else if(i==n&&j==1)//填加独立插头
				{
					if(q==3) continue;
					else if(q)//如果有上插头，插头消失，对应的右括号变为独立插头
					{
				    temp=change(s,find(s,j+1,1),3);
					temp=change(temp,j+1,0);
					push(k,temp,date);
					}
					
				}
				else if(!p&&q)
				{
					if(mp[i][j+1]) push(k,s,date);
					if(mp[i+1][j]) {
						temp=change(s,j,q);temp=change(temp,j+1,0);
						push(k,temp,date);
					}
				}
				else if(p&&!q)
				{
					if(mp[i][j+1]){
						temp=change(s,j,0);temp=change(temp,j+1,p);
						push(k,temp,date);
					}
					if(mp[i+1][j]) push(k,s,date);
				}
				else if(p==1&&q==2)
				{//形成了一个哈密尔顿回路，可是没什么鸟用
					continue;
				}
				else if (p==1&&(q==1||q==3))
				{
					temp=change(s,find(s,j+1,1),q);
					temp=change(temp,j,0);temp=change(temp,j+1,0);
					push(k,temp,date);
				}
				else if (p==2&&q==1)
				{
					temp=change(s,j,0);temp=change(temp,j+1,0);
					push(k,temp,date);
				}
				else if(p==2&&(q==2||q==3))
				{
					temp=change(s,find(s,j,-1),q);
					temp=change(temp,j,0);temp=change(temp,j+1,0);
					push(k,temp,date);
				}
				else if(p==3&&q==1)
				{
					temp=change(s,find(s,j+1,1),3);
					temp=change(temp,j,0);temp=change(temp,j+1,0);
					push(k,temp,date);
				}
				else if(p==3&&q==2)
				{
					temp=change(s,find(s,j,-1),3);
					temp=change(temp,j,0);temp=change(temp,j+1,0);
					push(k,temp,date);
				}
				else if(p==3&&q==3)
				{
					if(i==n&&j==n)
						ans+=date;
				}
			}
		}
		for(int km=0;km<f[k].size();km++) f[k][km].id<<=2;
	}
}
int main()
{
	freopen("betsy.in","r",stdin);
	freopen("betsy.out","w",stdout);
	scanf("%d",&n);
	if(n==1)
	{
	printf("%d",1);
	return 0;	
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			mp[i][j]=1;
	solve();
	printf("%d",ans);
	return 0;
}