151123(2)

Ruby


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

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

この条件を満たす経路の個数をD(i, j) と書く。
このとき、
D(mn, n) = 1 × (m + 1) × (2m + 1) × … × (m(n - 1) + 1)
（ただし、D(0, 0) = 1）
特に、m = 1 のとき、
D(mn, n) = D(n, n) = 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

M = 3
N = 8
[move1].each{|move|
  puts "move = #{move}のとき"
  (0..M).each{|m|
    puts "m = #{m}のとき"
    (0..N).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]]のとき
m = 0のとき
1
1
1
1
1
1
1
1
1
m = 1のとき
1
1
2
6
24
120
720
5040
40320
m = 2のとき
1
1
3
15
105
945
10395
135135
2027025
m = 3のとき
1
1
4
28
280
3640
58240
1106560
24344320