记录编号	83032	评测结果	AAAAAAA
题目名称	漫游小镇	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2013-11-29 13:41:32	内存使用	3.15 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<deque>
using namespace std;
const int MOD=4;//四进制储存信息
int n,m;//n是行数m是列数
int pow2[15]={1};
class STATE{
public:
	int x,y;
	map<int,int> f;
	void update(STATE&);
	void update(int,int);
	void clear(void){
		x=y=0;
		f.clear();
	}
	//first是括号表示法
	//左右括号表示连通的两插头,'#'表示无效
	//0表示无效,1表示左,2表示右
	//从右到左是2^0的数位到2^n的数位
}last,now;
bool plug_exi(int x,int y,int dir){
	//dir=1234分别表示上下左右
	if(dir==1&&x<=1) return false;
	if(dir==2&&x>=n) return false;
	if(dir==3&&y<=1) return false;
	if(dir==4&&y>=n) return false;
	return true;
}
//形如10,01,00,11
int getdigit(int &x,int k){//取四进制x的左零起第k位(将插头表示法视作string,则为x[k])
	int temp=2*(n-k);
	return (x&(pow2[temp]|pow2[temp+1]))>>temp;
}
void changedigit(int &x,int k,int a){//将四进制x的左零起第k位改成a
	x&=(~pow2[2*(n-k)]);
	x&=(~pow2[2*(n-k)+1]);
	x|=(a<<(2*(n-k)));
}
void printplug(int x){//调试接口,输出括号表示法的信息
	int i;
	for(i=0;i<=n;i++){
		cout<<getdigit(x,i);
	}
}
void addsum(map<int,int> &s,int lis,int t){//给lis的情况加上t
	map<int,int>::iterator key;
	key=s.find(lis);
	if(key==s.end()) s[lis]=t;
	else (key->second)+=t;
}
int findmatchl(int &x,int k){//与x的第k位(它是一个左括号)匹配的右括号位置
	int sum=1;//左括号个数-右括号个数
	int temp;
	while(true){
		temp=getdigit(x,++k);
		if(temp==1) sum++;
		else if(temp==2) sum--;
		if(sum==0) return k;
	}
	return -1;
}
int findmatchr(int &x,int k){//与x的第k位(它是一个右括号)匹配的左括号位置
	int sum=-1;//左括号个数-右括号个数
	int temp;
	while(true){
		temp=getdigit(x,--k);
		if(temp==1) sum++;
		else if(temp==2) sum--;
		if(sum==0) return k;
	}
	return -1;
}

void print(STATE st){//调试接口,输出某个DP状态
	cout<<st.x<<" "<<st.y<<endl;
	map<int,int>::iterator key;
	for(key=st.f.begin();key!=st.f.end();key++){
		printplug(key->first),cout<<":"<<(key->second)<<endl;
	}
	cout<<endl;
}
void STATE::update(int lis,int lt){//用值为lt的lis状态进行更新
	int now;
	int p,q;//p是左格的右插头,q是上格的下插头
	if(y!=1) p=getdigit(lis,y-1),q=getdigit(lis,y);
	else{
		p=0,q=getdigit(lis,0);
		lis>>=2;
	}
	if(plug_exi(x,y,2)&&plug_exi(x,y,4)){//有下插头和右插头
		if(p==0&&q==0){//新建分量
			now=lis;
			changedigit(now,y-1,1),changedigit(now,y,2);//p改成1,q改成2
			addsum(f,now,lt);
		}
	}
	if(p*q==0&&p+q!=0){
		if(plug_exi(x,y,2)){
			now=lis;
			changedigit(now,y-1,p+q);changedigit(now,y,0);
			addsum(f,now,lt);
		}
		if(plug_exi(x,y,4)){
			now=lis;
			changedigit(now,y-1,0);changedigit(now,y,p+q);
			addsum(f,now,lt);
		}
	}
	changedigit(lis,y-1,0);changedigit(lis,y,0);//因为是最后一种情况不会产生影响
	if(p&&q){//合并两个分量
		if(p==1&&q==1){
			now=lis;
			changedigit(now,findmatchl(now,y),1);
			addsum(f,now,lt);
		}
		else if(p==2&&q==2){
			now=lis;
			changedigit(now,findmatchr(now,y-1),2);
			addsum(f,now,lt);
		}
		else if(p==1&&q==2){
			if(x==n&&y==n){
				now=lis;
				changedigit(now,y-1,0),changedigit(now,y,0);
				addsum(f,now,lt);
			}
		}
		else if(p==2&&q==1){
			now=lis;
			addsum(f,now,lt);
		}
	}
}
void STATE::update(STATE &st){
	map<int,int>::iterator key;
	for(key=st.f.begin();key!=st.f.end();key++){
		update(key->first,key->second);
	}
}
void DP(void){
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			now.clear();
			now.x=i,now.y=j;
			now.update(last);
			last=now;
		}
	}
}
void answer(void){
	map<int,int>::iterator key;
	key=last.f.find(0);
	printf("%d\n",key->second);
}
void init(void){
	//将原图倒转90度,添上第0行,并且加一条"冖"型边以转化为回路问题
	scanf("%d",&n);
	last.x=0,last.y=n;
	int lis;
	int i;
	lis=1;//最左的下插头
	for(i=2;i<n;i++) lis*=MOD;lis+=0;//中间均为'#'
	lis*=MOD,lis+=2,lis*=MOD,lis+=0;//最右的")#"
	last.f[lis]=1;
	for(i=1;i<15;i++) pow2[i]=pow2[i-1]*2;
}
int main(){
	freopen("betsy.in","r",stdin);
	freopen("betsy.out","w",stdout);
	init();
	if(n==1){
		cout<<1<<endl;
		return 0;
	}
	DP();
	answer();
	return 0;
}