151127

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, 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}のとき"
n = 2
puts "n = 2 のとき"
(0..16).each{|m|
  used = Array.new((m * n + 1) * (2 * n + 1), false)
  p search(move, 0, 0, m, n, used)
}
n = 3
puts "n = 3 のとき"
(0..5).each{|m|
  used = Array.new((m * n + 1) * (2 * n + 1), false)
  p search(move, 0, 0, m, n, used)
}
n = 4
puts "n = 4 のとき"
(0..3).each{|m|
  used = Array.new((m * n + 1) * (2 * n + 1), false)
  p search(move, 0, 0, m, n, used)
}
n = 5
puts "n = 5 のとき"
(0..2).each{|m|
  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]]のとき
n = 2 のとき
1
3
9
29
95
313
1033
3411
11265
37205
122879
405841
1340401
4427043
14621529
48291629
159496415
n = 3 のとき
1
15
345
10199
317897
9947973
n = 4 のとき
1
153
95265
83918867
n = 5 のとき
1
4169
236871681