比赛 |
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;
}