pythonによる最短経路の数え上げプログラム

Question

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

path_keiro=list()
#これが０か１かで経路を通ったか判断
#path_keiro[i][j][0]はｘ＋１へ
#path_keiro[i][j][1]はｙ＋１へ
path_keiro=0　#初期化
i =int(0)
j=int(0)
#i,jはそれぞれ(x,y)座標の(i,j)とする
n=int(1)  #試しに１と置いてみました。
count=int(0)

def Ouro(i,j,path_keiro):

    if i==j==n: #行きの探索終了　パターンカウント
        count+=1
        return count

    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　#探索が終わったら帰ってくる。

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

print(count)

Comments

[jbpb0]

https://teratail.com/questions/189r666t2bwl5p
の回答でも指摘されてますが、関数「Ouro」は定義されてるだけで実行されてません

count=int(0)

のすぐ次に

print(count)

が実行されるので、

> countが０と表示され

となるのは当然です

Answer 1

別の質問でも回答していますが、このouroでは何も数えられません。

筋は悪くないのですが、大事なところが抜けています。

たとえば、もし、終端にたどりついたとしましょう。ouro(pythonの関数はすべて小文字が推奨です)は1を返します。
さて、この関数は1つ手前を探索しているouroから呼ばれていますが、その呼んだouro関数は、返ってきた1を受け取っていない=捨てています。
これでは数えられません。

方向性は、終点にだとり付いていない場合も値を返さなけれえばならなくて、その値は、左下から右上に行くとした場合、「ある点から終点への経路の数は右に進んだ数と上に進んだ数の合計」です。

Comments

[rikut0]

何度もお聞きして申し訳ありません。理解することが出来ました。ありがとうございました！