41 lines
924 B
Ruby
41 lines
924 B
Ruby
def cut_it(h, w)
|
|
if h.odd?
|
|
return 0 if w.odd?
|
|
h, w = w, h
|
|
end
|
|
return 1 if w == 1
|
|
|
|
nxt = [[w+1, 1, 0], [-w-1, -1, 0], [-1, 0, -1], [1, 0, 1]] # [next,dy,dx]
|
|
blen = (h + 1) * (w + 1) - 1
|
|
grid = [false] * (blen + 1)
|
|
|
|
walk = lambda do |y, x, count=0|
|
|
return count+1 if y==0 or y==h or x==0 or x==w
|
|
t = y * (w + 1) + x
|
|
grid[t] = grid[blen - t] = true
|
|
nxt.each do |nt, dy, dx|
|
|
count += walk[y + dy, x + dx] unless grid[t + nt]
|
|
end
|
|
grid[t] = grid[blen - t] = false
|
|
count
|
|
end
|
|
|
|
t = h / 2 * (w + 1) + w / 2
|
|
if w.odd?
|
|
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]
|
|
return count * 2 if h == w
|
|
count + walk[h / 2 - 1, w / 2]
|
|
end
|
|
end
|
|
|
|
for w in 1..9
|
|
for h in 1..w
|
|
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
|
|
end
|
|
end
|