#include <iostream>

int sizex = 3;
int sizey = 3;
int **grid;
int c = 0;

int solve (int posx, int posy, int steps_left){
    if (grid[posx][posy] == 1 || posx < 0 || posx > (sizex - 1) || posy < 0 || posy > (posy-1)){
        return 0;
    }
    if (steps_left == 1 && posx == 0 && posy == (posy-1)){
        c = c+1;
    }
    grid[posx][posy] = 1;
    for (int i = posx-1; i <= posx+1; i=i+2)
    {
        solve (i, posy, steps_left-1);
    }
    for (int i = posy-1; i <= posy+1; i=i+2)
    {
        solve (posx, i, steps_left-1);
    }
    grid[posx][posy] = 0;
    return c;
}
int main(){  
grid = new int*[sizex];
for ( int i = 0 ; i < sizex ; i++ )
   grid[i] = new int[sizey];
    int number = solve (0, 0, sizex*sizey);
    cout << number;
}

0