151129(2)

Ruby


正方形の形をした領域内のSelf-avoiding walk(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]]

def search(move, x, y, n, used)
  return 0 if n + 1 <= x.abs || n + 1 <= y.abs || used[x + n + (y + n) * (2 * n + 1)]
  return 1 if x.abs == n || y.abs == n
  cnt = 0
  used[x + n + (y + n) * (2 * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], n, used)
  }
  used[x + n + (y + n) * (2 * n + 1)] = false
  return cnt
end

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

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
1
4
92
115516
9731587524