68 lines
1.5 KiB
Text
68 lines
1.5 KiB
Text
require "table2"
|
|
local fmt = require "fmt"
|
|
|
|
local count <const> = {0}
|
|
local dir <const> = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
|
|
|
|
local function walk(y, x, h, w, grid, len, nxt)
|
|
if y == 0 or y == h or x == 0 or x == w then
|
|
count[1] += 2
|
|
return
|
|
end
|
|
local t = y * (w + 1) + x
|
|
grid[t + 1] += 1
|
|
grid[len - t + 1] += 1
|
|
for i = 1, 4 do
|
|
if grid[t + nxt[i] + 1] == 0 then
|
|
walk(y + dir[i][1], x + dir[i][2], h, w, grid, len, nxt)
|
|
end
|
|
end
|
|
grid[t + 1] -= 1
|
|
grid[len - t + 1] -= 1
|
|
end
|
|
|
|
local function cutrectangle(hh, ww, recur)
|
|
local h, w
|
|
if hh % 2 != 0 then
|
|
h, w = ww, hh
|
|
else
|
|
h, w = hh, ww
|
|
end
|
|
if h % 2 != 0 then
|
|
return 0
|
|
elseif w == 1 then
|
|
return 1
|
|
elseif w == 2 then
|
|
return h
|
|
elseif h == 2 then
|
|
return w
|
|
end
|
|
local cy = h // 2
|
|
local cx = w // 2
|
|
local len = (h + 1) * (w + 1)
|
|
local grid = table.rep(len, 0)
|
|
len -= 1
|
|
local nxt = {-1, -w - 1, 1, w + 1}
|
|
if recur then count[1] = 0 end
|
|
for x = cx + 1, w - 1 do
|
|
local t = cy * (w + 1) + x
|
|
grid[t + 1] = 1
|
|
grid[len - t + 1] = 1
|
|
walk(cy - 1, x, h, w, grid, len, nxt)
|
|
end
|
|
count[1] += 1
|
|
if h == w then
|
|
count[1] *= 2
|
|
elseif w % 2 == 0 and recur then
|
|
cutrectangle(w, h, false)
|
|
end
|
|
return count[1]
|
|
end
|
|
|
|
for y = 1, 10 do
|
|
for x = 1, y do
|
|
if x % 2 == 0 or y % 2 == 0 then
|
|
fmt.print($"%2d x %2d: %d", y, x, cutrectangle(y, x, true))
|
|
end
|
|
end
|
|
end
|