#include <stdio.h>
#include <time.h>
#define MAP_WIDTH 6
#define MAP_HEIGHT (MAP_WIDTH)
double g_count;
int g_map[MAP_HEIGHT+2][MAP_WIDTH+2];
void solve(int x, int y)
{
int nx, ny;
if(x==MAP_WIDTH && y==MAP_HEIGHT)
{
g_count+=1.0;
return;
}
nx=x+1;
ny=y+0;
if(!g_map[ny][nx])
{
g_map[ny][nx]=1;
solve(nx, ny);
g_map[ny][nx]=0;
}
if(y!=MAP_HEIGHT) // 袋小路の探索を省略
{
nx=x-1;
ny=y+0;
if(!g_map[ny][nx])
{
g_map[ny][nx]=1;
solve(nx, ny);
g_map[ny][nx]=0;
}
}
nx=x+0;
ny=y+1;
if(!g_map[ny][nx])
{
g_map[ny][nx]=1;
solve(nx, ny);
g_map[ny][nx]=0;
}
if(x!=MAP_WIDTH) // 袋小路の探索を省略
{
nx=x+0;
ny=y-1;
if(!g_map[ny][nx])
{
g_map[ny][nx]=1;
solve(nx, ny);
g_map[ny][nx]=0;
}
}
}
void solve_(void)
{
g_count=0;
if(MAP_HEIGHT==MAP_WIDTH)
{
g_map[1][1]=g_map[1][2]=1; // 対称性を考慮して最初に進む方向を決めうち
solve(2, 1);
g_count*=2; // 対角線について対称なので２倍
}
else
{
g_map[1][1]=1;
solve(1, 1);
}
}
int main(void)
{
clock_t s, e;
int i;
s=clock();
for(i=0;i<MAP_WIDTH+2;i++)
{
g_map[0][i]=g_map[MAP_HEIGHT+1][i]=1;
}
for(i=0;i<MAP_HEIGHT+2;i++)
{
g_map[i][0]=g_map[i][MAP_WIDTH+1]=1;
}
solve_();
e=clock();
printf("%.3f[sec]\n", (double)(e-s)/CLOCKS_PER_SEC);
printf("%.0f\n", g_count);
return 0;
}