151123(4)

Ruby


Dyck path とSelf-avoiding walk の融合(4)

原点(0, 0) から点(i, j) への最短経路で対角線を超えないものが
i x j 格子点上のDyck path であったが、
x 軸方向もy 軸方向も逆方向に進めるが、自身が通った点は通れないとしてみる。

この条件を満たす経路の個数をF(i, j) と書く。
F(mn, n) を出力してみる。

# -*- 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]]

# startがx, y、goalがmn, n
def search(move, x, y, m, n, used)
  return 0 if x < 0 || m * n + 1 <= x || y < 0 || m * y > x || used[x + y * (m * n + 1)]
  return 1 if x == m * n && y == n
  cnt = 0
  used[x + y * (m * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], m, n, used)
  }
  used[x + y * (m * n + 1)] = false
  return cnt
end

move = move3
puts "move = #{move3}のとき"
m = 0
puts "m = 0 のとき"
(0..8).each{|n|
  used = Array.new((m * n + 1) * (n + 1), false)
  p search(move, 0, 0, m, n, used)
}
m = 1
puts "m = 1 のとき"
(0..8).each{|n|
  used = Array.new((m * n + 1) * (n + 1), false)
  p search(move, 0, 0, m, n, used)
}
m = 2
puts "m = 2 のとき"
(0..6).each{|n|
  used = Array.new((m * n + 1) * (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) * (n + 1), false)
  p search(move, 0, 0, m, n, used)
}
m = 4
puts "m = 4 のとき"
(0..4).each{|n|
  used = Array.new((m * n + 1) * (n + 1), false)
  p search(move, 0, 0, m, n, used)
}
(5..8).each{|m|
  puts "m = #{m} のとき"
  (0..3).each{|n|
    used = Array.new((m * n + 1) * (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
1
m = 1 のとき
1
1
2
7
40
369
5680
150707
6993712
m = 2 のとき
1
1
4
44
1282
105022
25769912
m = 3 のとき
1
1
8
284
44360
m = 4 のとき
1
1
16
1872
1592536
m = 5 のとき
1
1
32
12384
m = 6 のとき
1
1
64
81856
m = 7 のとき
1
1
128
540736
m = 8 のとき
1
1
256
3571712