pythonによる最短経路のパターンカウントプログラム

Question

X-Y座標(0,0)から(ｎ,ｎ)までをマス?の境界を通り最短経路で往復する場合を考えます。
行きで通った経路は帰りでは通れません。
このとき、最短経路のパターンを数えるプログラムをpythonで作成したいです。
考えたプログラム構造としては、
行きと帰りの関数を作り、行きでは通った経路を記録していき探索を続け、(6,6)の地点に到達したら、帰りの関数を呼び出すプログラムを作ります。
帰りの関数では、行きの経路を避け探索し、経路を見つけたらカウントしていくプログラムを作ります。
以下のようにコードをなんとなくですが、作成してみました。
今回実行するとcountが０と表示されました。上手く動いていないことはわかるのですが、
どこをどのように改善すればよいのでしょうか。
ご助言よろしくお願いします。

path_keiro=list()
#これが０か１かで経路を通ったか判断
#path_keiro[i][j][0]はｘ＋１へ
#path_keiro[i][j][1]はｙ＋１へ
n=int(3)#今回は３とする
i =int(0)
j=int(0)
#i,jはそれぞれ(x,y)座標の(i,j)とする
count=int(0)

def Ouro(i,j,path_keiro):


    if i==j==ｎ: #行きの探索終了　帰りのプログラムを実行
        return kiro(i,j,path_keiro)

    elif i<ｎ and path_keiro[i][j][0]==0:
        path_keiro[i][j][0]=1
        Ouro(i+1,j,0)
        

    elif j<ｎ and path_keiro[i][j][1]==0:
        path_keiro[i][j][1]=1
        Ouro(i,j+1,0)

def kiro(i,j,path_keiro):
    if i==j==0:  #両方０のとき、往復完了でカウントする。
        count+=1
        return count

    elif i>0 and path_keiro[i-1][j][0]==0:
        path_keiro[i-1][j][0]=1
        kiro(i-1,j,0)

    elif j>0 and path_keiro[i][j-1][1]==0:
        path_keiro[i][j-1][1]=1
        kiro(i,j-1,0)

print(count)

Answer 1

コードにいろいろ問題があるように思います。

まず、これが本当のコードだとすると、関数が呼ばれておらず、最後の行でcountの値を表示しているのですから、初期値の0がプリントされているのはあたりまえですね。

path_keiroは初期化されていないので、突然「path_keiro[i][j][0]==0」のようにアクセスされるとエラーになりますね。

また、同じ場所を通るからといって、他の経路で使えないわけではないので、「path_keiro[i][j][0]==0」という判定もおかしいでしょうね。

まずは、[0, 0]から[n, n]までえの最短経路の総数を調べる関数、ouroをちゃんと作ってみるのがいいのではないかと思います。 ｎが3なら、20になりますよね。

Comments

[rikut0]

ご回答ありがとうございます。
同じ場所を通るからといって、他の経路で使えないわけではないので、「path_keiro[i][j][0]==0」という判定もおかしい
-->elif i<n and path_keiro[i][j][0]==0:
path_keiro[i][j][0]=1
Ouro(i+1,j,0)
path_keiro[i][j][0]=0　<<この部分！
のように探索が終わったら帰ってくるようにするのはどうでしょうか？
https://teratail.com/questions/0sizy1s7ifrwqy
こちらのリンクで、[0, 0]から[n, n]までえの最短経路の総数を調べる関数をつくりましたが、似たような問題が発生したので拝見して頂けると幸いです。
ご協力よろしくお願いいたします。

Answer 2

ご助言よろしくお願いします。

とりあえず単純なケースで実際にコードを動かしてみましょう。
それで正しい結果が出たら、少しずつ到達点を遠くしてみましょう。
そのため、到達点を表す値は6という実値でなく変数で与えるようにするとよいでしょう。

Comments

[rikut0]

ご助言ありがとうございます。変数に変更しました。実行時の出力は０となりました。
質問文を変更したので改めて、見ていただけると幸いです。