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