知恵袋で見つけた場合の数の道順問題をPythonで解いてみた。

 知恵袋で見つけた場合の数の道順問題Pythonで解いてみました。(^_^;

 図のような道路がある町において、道路を進む際、進むことのできる道路の方向が東方向、北方向および北東方向の3方向に限られているとき、図のA地点からB地点を経由してC地点へ行く道順は何通りあるか。
(1) 65通り (2) 78通り (3) 84通り (4) 91通り (5) 98通り

+-+-+-C        N
|/|/|/|       /|
+-+-+-+      *-+--
|/|/|/|        |
+-+-+-+        |
|/|/|/|
+-+-B-+
|/|/|/|
+-+-+-+
|/|/|/|
A-+-+-+

 最短なら斜め(/)をできるだけ多く通った方がいいから、最短経路とはちょっと違うけど、拙ブログの「最短経路の場合の数の問題をJavaで解いてみた。」を参考にして作りました。(^_^;
 ちなみに、自分で解く場合は、拙プログラムのように、逐次足し算でやる方法と、斜め(/)を通る回数(0,1,2)で場合分けする方法があります。

● NumOfPath1.py

# coding: UTF-8
# NumOfPath1.py

from time import time

sMap = [

    "     +-C",
    "     |/|",
    "     +-+",
    "     |/|",
    "     +-+",
    "     |/|",
    " +-+-B-+",
    " |/|/|  ",
    " +-+-+  ",
    " |/|/|  ",
    " A-+-+  ",
    "        ",
]

def main():
    tm = time() # Timer Start
    m,n = len(sMap),len(sMap[0])
    iMap = [[0 for i in range(n)] for j in range(m)]
##    print(m,n); print(iMap)
    # s/g型のsMapからs\g型のiMapを作成
    for i in range(m):
        for j in range(n):
            if sMap[i][j] in '|-/':
                iMap[m-1-i][j] = 1
##    print(iMap)
    # 逐次足し算
    iMap[1][1] = 1      # 和の初期値。StartのAだけ1、他の点は0
    for i in range(1,m,2):
        for j in range(1,n,2):
            if iMap[i  ][j-1]==1: iMap[i][j]+=iMap[i  ][j-2]
            if iMap[i-1][j  ]==1: iMap[i][j]+=iMap[i-2][j  ]
            if iMap[i-1][j-1]==1: iMap[i][j]+=iMap[i-2][j-2]
    # 結果の表示
    for i in reversed(range(1,m,2)):
        for j in range(1,n,2):
            print("%4d"%iMap[i][j],end='')
        print()
    print()

    print("∴%d"%iMap[m-1][n-1])
    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

   0   0  13  91
   0   0  13  65
   0   0  13  39
   1   5  13  13
   1   3   5   0
   1   1   1   0

∴91
Runtime : 0.001 [sec]

※参考URL
道順が何通りあるか考える問題について質問です。 - 碁盤のマスの... - Yahoo!知恵袋
高校数学【場合の数と確率】〈最短経路の数〉図(一番下の画像)の... - Yahoo!知恵袋
最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
立体の最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
立体の最短経路の場合の数の問題をJavaで解いてみた。(2) - rscのブログ