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

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

　AからBまで行く最短経路は全部で何通りですか。
ただし、X地点は通ることができず、Y地点は直進しかできないものとする。

 +-+-+-+-+-+-B
 | | | | | | |
 +-+-+-+-+-+-+
 | | | | | | |
 +-+-+-+-Y-+-+
 | | | | | | |
 +-+-X-+-+-+-+
 | | | | | | |
 A-+-+-+-+-+-+

　拙ブログの記事中のプログラムを雛形にして作りました。(^_^;
　[S／G]型(左下スタート、右上ゴール)のsMapから[S＼G]型(左上スタート、右下ゴール)のsMapへの変換と、sMapからiMapの作成を分けてみました。(cf.)
　それから、Y地点の条件をどう表すかが難しかったです。

● NumOfShortestPath3.py

# coding: UTF-8
# NumOfShortestPath3.py

from time import time

sMap = [
    " +-+-+-+-+-+-B",
    " | | | | | | |",
    " +-+-+-+-+-+-+",
    " | | | | * | |",
    " +-+-+-+ Y*+-+",
    " | |   |   | |",
    " +-+ X +-+-+-+",
    " | |   | | | |",
    " 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型のsMapへ変換
    for i in range(m//2):
        sMap[i],sMap[m-1-i] = sMap[m-1-i],sMap[i]   # swap
##    print(sMap)
    # 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
            if sMap[i][j] in '*':
                iMap[i][j] = 2
##    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  ][j-1]==2: iMap[i][j]+=iMap[i  ][j-4]
            if iMap[i-1][j  ]==2: iMap[i][j]+=iMap[i-4][j  ]
    # 結果の表示
    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()

●実行結果

   1   5  12  23  36  56  87
   1   4   7  11  13  20  31
   1   3   3   4   0   7  11
   1   2   0   1   2   3   4
   1   1   1   1   1   1   1

∴87
Runtime : 0.000 [sec]

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