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.

F cut_it(=h, =w)
   V dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
   I h % 2 != 0
      swap(&h, &w)
   I h % 2 != 0
      R 0
   I w == 1
      R 1
   V count = 0
 
   V next = [w + 1, -w - 1, -1, 1]
   V blen = (h + 1) * (w + 1) - 1
   V grid = [0B] * (blen + 1)
 
   F walk(Int y, x, =count) -> Int
      I y == 0 | y == @h | x == 0 | x == @w
         R count + 1
 
      V t = y * (@w + 1) + x
      @grid[t] = @grid[@blen - t] = 1B
 
      L(i) 4
         I !@grid[t + @next[i]]
            count = @walk(y + @dirs[i][0], x + @dirs[i][1], count)
 
      @grid[t] = @grid[@blen - t] = 0B
      R count
 
   V t = h I/ 2 * (w + 1) + w I/ 2
   I w % 2 != 0
      grid[t] = grid[t + 1] = 1B
      count = walk(h I/ 2, w I/ 2 - 1, count)
      V res = count
      count = 0
      count = walk(h I/ 2 - 1, w I/ 2, count)
      R res + count * 2
   E
      grid[t] = 1B
      count = walk(h I/ 2, w I/ 2 - 1, count)
      I h == w
         R count * 2
      count = walk(h I/ 2 - 1, w I/ 2, count)
      R count
 
L(w) 1..9
   L(h) 1..w
      I (w * h) % 2 == 0
         print(‘#. x #.: #.’.format(w, h, cut_it(w, h)))