知恵袋で見つけた最短経路の問題をPythonで解いてみた。(2)

　知恵袋で見つけた最短経路の問題をPythonで解いてみました。(^_^;

　図のような経路で、点Aを出発して点Pを通り点Bへ行く最短経路は何通りあるか。
(1)40通り　(2)48通り　(3)54通り　(4)60通り　(5)72通り

 A-+-+-+-+-+-+
 | | | | | | |
 +-+-+ +-+-+-+
 | |     | | |
 +-+-+ +-+-+-+
 | | | | | | |
 +-+-+-+-P-+-+
 | | | | | | |
 +-+-+-+-+-+-+
 | | | | | | |
 +-+-+-+-+-+-B

　拙ブログの記事中のプログラムを雛形にして作りました。(^_^;
　問題が、[S＼G]型(左上スタート、右下ゴール)になっているので、[S／G]型(左下スタート、右上ゴール)から、[S＼G]型への変換はしなくても済みました。(cf.)

● NumOfShortestPath2.py

# coding: UTF-8
# NumOfShortestPath2.py

from time import time

sMap = [
    "              ",
    " A-+-+-+-+    ",
    " | | | | |    ",
    " +-+-+ +-+    ",
    " | |     |    ",
    " +-+-+ +-+    ",
    " | | | | |    ",
    " +-+-+-+-P-+-+",
    "         | | |",
    "         +-+-+",
    "         | | |",
    "         +-+-B",
]

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[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  ]
    # 結果の表示
    for i in 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()

●実行結果

   1   1   1   1   1   0   0
   1   2   3   1   2   0   0
   1   3   3   0   2   0   0
   1   4   7   7   9   9   9
   0   0   0   0   9  18  27
   0   0   0   0   9  27  54

∴54
Runtime : 0.000 [sec]

※参考URL
●知恵袋で見つけた最短経路の問題をPythonで解いてみた。 - rscのブログ
●最短経路の場合の数の問題をJavaで解いてみた。 - rscのブログ
●知恵袋で見つけた場合の数の道順問題をPythonで解いてみた。 - rscのブログ