151128(4)

Ruby


正方形の形をした領域内のSelf-avoiding walk(2)

経路の長さで分けてみる。

# -*- 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, depth)
  ary0 = Array.new((2 * n - 1) * (2 * n - 1) + 1, 0)
  return ary0 if n + 1 <= x.abs || n + 1 <= y.abs || used[x + n + (y + n) * (2 * n + 1)]
  if x.abs == n || y.abs == n
    ary0[depth] = 1
    return ary0
  end
  c_ary = Array.new((2 * n - 1) * (2 * n - 1) + 1, 0)
  used[x + n + (y + n) * (2 * n + 1)] = true
  move.each{|mo|
    ary1 = search(move, x + mo[0], y + mo[1], n, used, depth + 1)
    c_ary = (0..(2 * n - 1) * (2 * n - 1)).map{|i| c_ary[i] + ary1[i]}
  }
  used[x + n + (y + n) * (2 * n + 1)] = false
  return c_ary
end

N = 3
move = move3
puts "move = #{move3}のとき"
(0..N).each{|n|
  used = Array.new((2 * n + 1) * (2 * n + 1), false)
  a_ary = search(move, 0, 0, n, used, 0)
  p [a_ary.inject(:+), a_ary]
}

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
[1, [1, 0]]
[4, [0, 4]]
[92, [0, 0, 4, 16, 8, 16, 8, 16, 8, 16]]
[115516, [0, 0, 0, 4, 24, 72, 80, 176, 200, 472, 568, 1368, 1584, 3664, 4000, 8696, 8392, 16528, 12704, 21504, 10616, 14352, 4528, 4576, 888, 520]]