151125(2)

Ruby


二等辺三角形の形をした領域内のSelf-avoiding walk(2)

点の集合Dを
格子点で0 ≦ x ≦ mn, x / m ≧ y ≧ - x / mを満たしているもの
とする。
今、Dの点(0, 0)から出発し、
自身が通った点を通ることなく、左右上下に進みながら
(mn, n - 1), (mn, n -2), … , (mn, -(n - 1))
のいずれか一つへたどることとする。
このたどり方が何通りあるか出力してみる。

# -*- 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, m, n, used)
  return 0 if x < 0 || m * n + 1 <= x || - m * y > x || m * y > x || used[x + (y + n) * (m * n + 1)]
  return 1 if x == m * n
  cnt = 0
  used[x + (y + n) * (m * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], m, n, used)
  }
  used[x + (y + n) * (m * n + 1)] = false
  return cnt
end

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

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
m = 0 のとき
1
1
1
1
1
1
1
1
m = 1 のとき
1
1
3
15
153
4169
346211
86336255
m = 2 のとき
1
1
9
345
95265
m = 3 のとき
1
1
29
10199
83918867
m = 4のとき
1
1
95
317897
m = 5のとき
1
1
313
9947973