Description
Smith在P市的邮政局工作，他每天的工作是从邮局出发，到自己所管辖的所有邮筒取信件，然后带回邮局。他所管辖的邮筒非常巧地排成了一个m*n的点阵（点阵中的间距都是相等的）。左上角的邮筒恰好在邮局的门口。 Smith是一个非常标新立异的人，他希望每天都能走不同的路线，但是同时，他又不希望路线的长度增加，他想知道他有多少条不同的路线可走。【任务描述】你的程序需要根据给定的输入，给出符合题意的输出： 输入包括点阵的m和n的值； 你需要根据给出的输入，计算出Smith可选的不同路线的总条数；
Input
只有一行。包括两个整数m, n(1 <= m <= 10, 1 <= n <= 20)，表示了Smith管辖内的邮筒排成的点阵。
Output
只有一行，只有一个整数，表示Smith可选的不同路线的条数。
Sample Input
2 2
说明：该输入表示，Smith管辖了2*2的一个邮筒点阵。
说明：该输入表示，Smith管辖了2*2的一个邮筒点阵。
Sample Output
2
裸插头dp
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int bi=;
int i;
struct na{
int x,z;
na(int xx,int zz):x(xx),z(zz){}
};
struct big{
int a[];
big(){
memset(a,,sizeof(a));
a[]=;
}
big operator =(int x){
if (x==){
memset(a,,sizeof(a));
a[]=;
return *this;
}
a[]=;
while (x){
a[]++;
a[a[]]=x%bi;
x/=bi;
}
if (!a[]) a[]=;
return *this;
}
big operator +(const big &x){
big r;
if (a[]<x.a[]) r.a[]=x.a[];else r.a[]=a[];
for (i=;i<=r.a[];i++) r.a[i]=a[i]+x.a[i];
for (i=;i<=r.a[];i++)
if (r.a[i]>=bi){
r.a[i]-=bi;r.a[i+]++;
if (i==r.a[]) r.a[]++;
}
return r;
}
}ans;
int n,m,x,y,z,a[],k,p1,p2;
bool map[][];
big f[][];
int v[][];
queue <na> q;
inline int gx(int x,int q1,int q2){k=;for (register int i=m+;i;i--) k=k*+(i==x?q1:(i==x+?q2:a[i]));return k;}
inline void up(int x,int z,big lj){
x++;
k=x%;
if (v[k][z]!=x) v[k][z]=x,f[k][z]=,q.push(na(x,z));
f[k][z]=f[k][z]+lj;
}
int main(){
register int i,j;
scanf("%d%d",&n,&m);
if (n<m) swap(n,m);
for (i=;i<=m;i++)
for (j=;j<=n;j++)
map[i][j]=;
f[][]=v[][]=;
q.push(na(,));
while(!q.empty()){
na no=q.front();q.pop();
big an=f[no.x%][no.z];
if(no.x%m==) no.z*=;
x=no.x%m+;y=no.x/m+;
for (i=;i<=m+;i++) a[i]=;
for (i=,j=no.z;j;i++,j/=) a[i]=j%;
if (!map[x][y]) up(no.x,gx(x,,),an);else
if (a[x]==&&a[x+]==){
if (x==m&&y==n) ans=ans+an;
}else if (a[x]==&&a[x+]==) up(no.x,gx(x,,),an);else
if (a[x]==&&a[x+]==){
if (map[x][y+]&&map[x+][y]) up(no.x,gx(x,,),an);
}else if (a[x]==){
if (map[x+][y]) up(no.x,gx(x,,a[x+]),an);
if (map[x][y+]) up(no.x,gx(x,a[x+],),an);
}else if (a[x+]==){
if (map[x+][y]) up(no.x,gx(x,,a[x]),an);
if (map[x][y+]) up(no.x,gx(x,a[x],),an);
}else if (a[x]==a[x+]){
p1=p2=;
if (a[x]==)
for (j=,i=x+;i<=m;i++){
if (a[i]==) j--;
if (a[i]==) j++;
if (j>&&!p1) p1=i,j--;
if (j>&&p1){p2=i;break;}
}else
for (j=,i=x-;i;i--){
if (a[i]==) j++;
if (a[i]==) j--;
if (j>&&!p2) p2=i,j--;
if (j>&&p2){p1=i;break;}
}
a[p1]=;a[p2]=;up(no.x,gx(x,,),an);
}
}
ans=ans+ans;
if (ans.a[]==&&ans.a[]==) printf("1\n");else{
printf("%d",ans.a[ans.a[]]);
for (i=ans.a[]-;i;i--) printf("%09d",ans.a[i]);
}
}