151121(3)

Ruby


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

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

@move0 = [[1, 0], [0, 1]]
@move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def binomial_theorem(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x + y == n - 1
  cnt = 0
  used[x + y * n] = true
  @move0.each{|m|
    cnt += binomial_theorem(x + m[0], y + m[1], n, used)
  }
  used[x + y * n] = false
  return cnt
end

# startがx, y、goalの座標の和がn - 1
def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x + y == n - 1
  cnt = 0
  used[x + y * n] = true
  @move.each{|m|
    cnt += search(x + m[0], y + m[1], n, used)
  }
  used[x + y * n] = false
  return cnt
end

# 確認用
(1..10).each{|n|
  used = Array.new(n * n, false)
  p binomial_theorem(0, 0, n, used)
}

(1..10).each{|n|
  used = Array.new(n * n, false)
  p search(0, 0, n, used)
}

出力結果
1
2
4
8
16
32
64
128
256
512
1
2
4
12
48
288
2768
45408
1289000
63234984