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.

import strformat
 
var
  w, h: int
  grid: seq[byte]
  next: array[4, int]
  count: int
 
const Dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
 
template odd(n: int): bool = (n and 1) != 0
 
#------------------------------------------------------------------------------
 
proc walk(y, x: int) =
 
  if y == 0 or y == h or x == 0 or x == w:
    inc count, 2
    return
 
  let t = y * (w + 1) + x
  inc grid[t]
  inc grid[grid.high - t]
 
  for i, dir in Dirs:
    if grid[t + next[i]] == 0:
      walk(y + dir[0], x + dir[1])
 
  dec grid[t]
  dec grid[grid.high - t]
 
#------------------------------------------------------------------------------
 
proc solve(y, x: int; recursive: bool): int =
 
  h = y
  w = x
  if odd(h): swap w, h
 
  if odd(h): return 0
  if w == 1: return 1
  if w == 2: return h
  if h == 2: return w
 
  let cy = h div 2
  let cx = w div 2
 
  grid = newSeq[byte]((w + 1) * (h + 1))
 
  next[0] = -1
  next[1] = -w - 1
  next[2] = 1
  next[3] = w + 1
 
  if recursive: count = 0
 
  for x in (cx + 1)..<w:
    let t = cy * (w + 1) + x
    grid[t] = 1
    grid[grid.high - t] = 1
    walk(cy - 1, x)
  inc count
 
  if h == w:
    count *= 2
  elif not odd(w) and recursive:
    discard solve(w, h, false)
 
  result = count
 
#——————————————————————————————————————————————————————————————————————————————
 
for y in 1..10:
  for x in 1..y:
    if not odd(x) or not odd(y):
      echo &"{y:2d} x {x:2d}: {solve(y, x, true)}"