60 lines
1.6 KiB
Text
60 lines
1.6 KiB
Text
def dir: [[0, -1], [-1, 0], [0, 1], [1, 0]] ;
|
|
|
|
# input and output: {grid, w, h, len, count, next}
|
|
def mywalk($y; $x):
|
|
if ($y == 0 or $y == .h or $x == 0 or $x == .w)
|
|
then .count += 2
|
|
else ($y * (.w + 1) + $x) as $t
|
|
| .grid[$t] += 1
|
|
| .grid[.len-$t] += 1
|
|
| reduce range(0; 4) as $i (.;
|
|
if .grid[$t + .next[$i]] == 0
|
|
then mywalk($y + dir[$i][0]; $x + dir[$i][1])
|
|
else .
|
|
end )
|
|
| .grid[$t] += -1
|
|
| .grid[.len-$t] += -1
|
|
end;
|
|
|
|
# solve/3 returns an integer.
|
|
# If $count is null, the value is the count of permissible cuts for an $h x $w rectangle.
|
|
# Otherwise, the computed value augments $count.
|
|
def solve($h; $w; $count):
|
|
if $count then {$count} else {} end
|
|
| if $h % 2 == 0
|
|
then . + {$h, $w}
|
|
else . + {w: $h, h: $w} # swap
|
|
end
|
|
| if (.h % 2 == 1) then 0
|
|
elif (.w == 1) then 1
|
|
elif (.w == 2) then .h
|
|
elif (.h == 2) then .w
|
|
else ((.h/2)|floor) as $cy
|
|
| ((.w/2)|floor) as $cx
|
|
| .len = (.h + 1) * (.w + 1)
|
|
| .grid = [range(0; .len) | 0]
|
|
| .len += -1
|
|
| .next = [-1, - .w - 1, 1, .w + 1]
|
|
| .x = $cx + 1
|
|
| until (.x >= .w;
|
|
($cy * (.w + 1) + .x) as $t
|
|
| .grid[$t] = 1
|
|
| .grid[.len-$t] = 1
|
|
| mywalk($cy - 1; .x)
|
|
| .x += 1 )
|
|
| .count += 1
|
|
| if .h == .w
|
|
then .count * 2
|
|
elif (.w % 2 == 0) and $count == null
|
|
then solve(.w; .h; .count)
|
|
else .count
|
|
end
|
|
end ;
|
|
|
|
def task($n):
|
|
range (1; $n+1) as $y
|
|
| range(1; $y + 1) as $x
|
|
| select(($x % 2 == 0) or ($y % 2 == 0))
|
|
| "\($y) x \($x) : \(solve($y; $x; null))" ;
|
|
|
|
task(10)
|