69 lines
1.4 KiB
Plaintext
69 lines
1.4 KiB
Plaintext
const count = [0]
|
|
const dir = [[0, -1], [-1, 0], [0, 1], [1, 0]]
|
|
|
|
function walk(y, x, h, w, grid, len, next)
|
|
if y == 0 || y == h || x == 0 || x == w
|
|
count[1] += 2
|
|
return
|
|
end
|
|
t = y * (w + 1) + x
|
|
grid[t + 1] += UInt8(1)
|
|
grid[len - t + 1] += UInt8(1)
|
|
for i in 1:4
|
|
if grid[t + next[i] + 1] == 0
|
|
walk(y + dir[i][1], x + dir[i][2], h, w, grid, len, next)
|
|
end
|
|
end
|
|
grid[t + 1] -= 1
|
|
grid[len - t + 1] -= 1
|
|
end
|
|
|
|
function cutrectangle(hh, ww, recur)
|
|
if isodd(hh)
|
|
h, w = ww, hh
|
|
else
|
|
h, w = hh, ww
|
|
end
|
|
if isodd(h)
|
|
return 0
|
|
elseif w == 1
|
|
return 1
|
|
elseif w == 2
|
|
return h
|
|
elseif h == 2
|
|
return w
|
|
end
|
|
cy = div(h, 2)
|
|
cx = div(w, 2)
|
|
len = (h + 1) * (w + 1)
|
|
grid = zeros(UInt8, len)
|
|
len -= 1
|
|
next = [-1, -w - 1, 1, w + 1]
|
|
if recur
|
|
count[1] = 0
|
|
end
|
|
for x in cx + 1:w - 1
|
|
t = cy * (w + 1) + x
|
|
grid[t + 1] = 1
|
|
grid[len - t + 1] = 1
|
|
walk(cy - 1, x, h, w, grid, len, next)
|
|
end
|
|
count[1] += 1
|
|
if h == w
|
|
count[1] *= 2
|
|
elseif iseven(w) && recur
|
|
cutrectangle(w, h, false)
|
|
end
|
|
return count[1]
|
|
end
|
|
|
|
function runtest()
|
|
for y in 1:10, x in 1:y
|
|
if iseven(x) || iseven(y)
|
|
println("$y x $x: $(cutrectangle(y, x, true))")
|
|
end
|
|
end
|
|
end
|
|
|
|
runtest()
|