83 lines
1.4 KiB
Go
83 lines
1.4 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
var grid []byte
|
|
var w, h, last int
|
|
var cnt int
|
|
var next [4]int
|
|
var dir = [4][2]int{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
|
|
|
|
func walk(y, x int) {
|
|
if y == 0 || y == h || x == 0 || x == w {
|
|
cnt += 2
|
|
return
|
|
}
|
|
t := y*(w+1) + x
|
|
grid[t]++
|
|
grid[last-t]++
|
|
for i, d := range dir {
|
|
if grid[t+next[i]] == 0 {
|
|
walk(y+d[0], x+d[1])
|
|
}
|
|
}
|
|
grid[t]--
|
|
grid[last-t]--
|
|
}
|
|
|
|
func solve(hh, ww, recur int) int {
|
|
h = hh
|
|
w = ww
|
|
|
|
if h&1 != 0 {
|
|
h, w = w, h
|
|
}
|
|
switch {
|
|
case h&1 == 1:
|
|
return 0
|
|
case w == 1:
|
|
return 1
|
|
case w == 2:
|
|
return h
|
|
case h == 2:
|
|
return w
|
|
}
|
|
cy := h / 2
|
|
cx := w / 2
|
|
|
|
grid = make([]byte, (h+1)*(w+1))
|
|
last = len(grid) - 1
|
|
next[0] = -1
|
|
next[1] = -w - 1
|
|
next[2] = 1
|
|
next[3] = w + 1
|
|
|
|
if recur != 0 {
|
|
cnt = 0
|
|
}
|
|
for x := cx + 1; x < w; x++ {
|
|
t := cy*(w+1) + x
|
|
grid[t] = 1
|
|
grid[last-t] = 1
|
|
walk(cy-1, x)
|
|
}
|
|
cnt++
|
|
|
|
if h == w {
|
|
cnt *= 2
|
|
} else if w&1 == 0 && recur != 0 {
|
|
solve(w, h, 0)
|
|
}
|
|
return cnt
|
|
}
|
|
|
|
func main() {
|
|
for y := 1; y <= 10; y++ {
|
|
for x := 1; x <= y; x++ {
|
|
if x&1 == 0 || y&1 == 0 {
|
|
fmt.Printf("%d x %d: %d\n", y, x, solve(y, x, 1))
|
|
}
|
|
}
|
|
}
|
|
}
|