151124

Ruby


Dyck path とSelf-avoiding walk の融合(7)

F(3m, 3) について、もう一つ値が求まった。

# -*- coding: cp932 -*-

move0 = [[1, 0], [0, 1]]
move1 = [[1, 0], [-1, 0], [0, 1]]
move2 = [[1, 0], [0, 1], [0, -1]]
move3 = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# startがx, y、goalがmn, n
def search(move, x, y, m, n, used)
  return 0 if x < 0 || m * n + 1 <= x || y < 0 || m * y > x || used[x + y * (m * n + 1)]
  return 1 if x == m * n && y == n
  cnt = 0
  used[x + y * (m * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], m, n, used)
  }
  used[x + y * (m * n + 1)] = false
  return cnt
end

move = move3
puts "move = #{move3}のとき"
(0..11).each{|m|
  n = 3
  used = Array.new((m * n + 1) * (n + 1), false)
  p search(move, 0, 0, m, n, used)
}

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
1
7
44
284
1872
12384
81856
540736
3571712
23592704
155842560
1029427200