A floor of size 8x8 has to be covered by bricks of size 1x2. How many ways are there to layout bricks in the floor? Generalize the problem to the floo

A floor of size 8x8 has to be covered by bricks of size 1x2. How many ways are there to layout bricks in the floor? Generalize the problem to the floor of size MxN and bricks of size PxQ each.

int foo(int n,int x,int y)
{
if(x>=n||y>=n)
return 0;
if(x==n-1&&y==n-1)
return 1;
return foo(n,x+2,y+0)+foo(n,x+1,y+1)+foo(n,x+0,y+1)+foo(n,x+0,y+2)+foo(n,x+1,y+0);
}