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.

 
class
	APPLICATION
 
create
	make
 
feature {NONE} -- Initialization
 
	make
			-- Finds solution for cut a rectangle up to 10 x 10.
		local
			i, j, n: Integer
			r: GRID
		do
			n := 10
			from
				i := 1
			until
				i > n
			loop
				from
					j := 1
				until
					j > i
				loop
					if i.bit_and (1) /= 1 or j.bit_and (1) /= 1 then
						create r.make (i, j)
						r.print_solution
					end
					j := j + 1
				end
				i := i + 1
			end
		end
 
end
 