#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,ox,oy,m[50][50]; long long ras,cate; const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; void bck(int k,int i,int j) { if(k==n-1) { ras++; return ; } if(m[ox-1][oy]==0) { m[ox-1][oy]=1; bck(k+1,ox-1,oy); m[ox-1][oy]=0; } if(k==0&&m[ox][oy+1]==0) { m[ox][oy+1]=1; bck(k+1,ox,oy+1); m[ox][oy+1]=0;return; } int nx,ny; for(int o=0;o<4;o++) { nx=i+dx[o]; ny=j+dy[o]; if(m[nx][ny]==0) { if(ny==oy&&nx>ox)continue; if(ny<oy)continue; m[nx][ny]=1; bck(k+1,nx,ny); m[nx][ny]=0; } } } int main() { //freopen("input","r",stdin); //freopen("output","w",stdout); scanf("%d",&n); ox=15; oy=15; m[ox][oy]=1; bck(0,ox,oy); printf("%lld",ras); return 0; } /*#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m[50][50]; long long ras,cate; const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; void bck(int k,int i,int j,int mx,int my) { if(k==n-1) { ras++; return ; } int nx,ny; int xmax,ymax; for(int o=0;o<4;o++) { nx=i+dx[o]; ny=j+dy[o]; if(m[nx][ny]==0) { m[nx][ny]=1; xmax=mx; ymax=my; if(xmax>nx) { xmax=nx; ymax=ny; } else if(xmax==nx&&ymax<ny) { xmax=nx; ymax=ny; } bck(k+1,nx,ny,xmax,ymax); m[nx][ny]=0; } } } int main() { //freopen("input","r",stdin); //freopen("output","w",stdout); scanf("%d",&n); ox=15; oy=15; m[ox][oy]=1; bck(0,ox,oy,ox,oy); printf("%lld",ras-cate/2); return 0; } */