A given rectangle is made from m × n squares. If m and n are not both odd, then it is possible to cut a path through the rectangle along the square edges such that the rectangle splits into two connected pieces with the same shape (after rotating one of the pieces by 180°). All such paths for 2 × 2 and 4 × 3 rectangles are shown below.



Write a program that calculates the number of different ways to cut an m × n rectangle. Optionally, show each of the cuts.

Possibly related task: Maze generation for depth-first search.

fcn cut_it(h,w){
   if(h.isOdd){
      if(w.isOdd) return(0);
      t,h,w=h,w,t;  // swap w,h: a,b=c,d --> a=c; b=d; so need a tmp
   }
   if(w==1) return(1);
 
   nxt :=T(T(w+1, 1,0), T(-w-1, -1,0), T(-1, 0,-1), T(1, 0,1)); #[next, dy,dx]
   blen:=(h + 1)*(w + 1) - 1;
   grid:=(blen + 1).pump(List(),False); //-->L(False,False...)
 
   walk:='wrap(y,x){ // lambda closure
      if(y==0 or y==h or x==0 or x==w) return(1);
      count,t:=0,y*(w + 1) + x;
      grid[t]=grid[blen - t]=True;
      foreach nt,dy,dx in (nxt){
         if(not grid[t + nt]) count+=self.fcn(y + dy, x + dx,vm.pasteArgs(2));
      }
      grid[t]=grid[blen - t]=False;
      count
   };
 
   t:=h/2*(w + 1) + w/2;
   if(w.isOdd){
      grid[t]=grid[t + 1]=True;
      count:=walk(h/2, w/2 - 1);
      count + walk(h/2 - 1, w/2)*2;
   }else{
      grid[t]=True;
      count:=walk(h/2, w/2 - 1);
      if(h==w) return(count*2);
      count + walk(h/2 - 1, w/2);
   }
}