今週のお題：目標を達成する手順は何通り？

ちょっと気力を使ったので・・・。

https://codeiq.jp/challenge/3302

例えば、横に m マス、縦に n マスの格子状のマスを左上から右下に移動するための手順を考える、という例があります。 使用可能な操作は「前に進む」「左を向く」「右を向く」の3つです。 このマスの外側には移動できず、最短の経路である必要はありません。

なお、右下のマスに着くとその時点で終了とします。 （つまり、右下のマスでは「左を向く」「右を向く」の操作はできません。）

m = 3, n = 2で、右向きに開始するとき、以下の4回の操作で左図のように移動できます。 1. 前に進む 2. 前に進む 3. 右を向く 4. 前に進む

イメージ

では、左上から右下に5回の操作で移動させるにはどうすればよいでしょうか？

状態をmn4方向の3次元行列で表現する。添字のスライスの仕方がnumpy風にいかずデバッグが難航。 表示は大切。 使う盤面をステップ毎にコピーするとO(Nmn)になり、1つのケースだけ間に合わないので、 2種類の盤面を交互に使いまわすが、新しい盤面をreturnして古い盤面に参照渡ししてしまっていて、 ハマった。

import numpy as np

def is_inner(x):
    global m,n

    if 1<=x[0] and x[0]<=m and 1<=x[1] and x[1]<=n:
        return True
    return False

def mdist(i,j,a,b):
    global m,n
    return np.abs(i-a)+np.abs(j-b)

def generatenext(states,nstates):
    global m,n,N,step

    count=0
    for i in range(1,m+1):
        for j in range(max(1,n-(N-step)+np.abs(m-i)-1),min(step-np.abs(i-1)+3,n+1)):
            if i==m and j==n:
                if step<N-2:
                    continue

            statesback=states[i][j][:]
            nstates[i][j][0]=states[i-1][j][0]
            nstates[i][j][1]=states[i][j-1][1]
            nstates[i][j][2]=states[i+1][j][2]
            nstates[i][j][3]=states[i][j+1][3]

            for k in range(4):
                nstates[i][j][(k-1)%4]+=statesback[k]
                nstates[i][j][(k+1)%4]+=statesback[k]

    return nstates,states


n,m,N=list(map(int,input().split(" ")))

states=[[[0 for k in range(4)] for j in range(n+2)] for i in range(m+2)]
nstates=[[[0 for k in range(4)] for j in range(n+2)] for i in range(m+2)]

for k in range(4):
    states[1][1][k]=1

for k in range(N):
    step=k
    if k%2==0:
        nstates,states=generatenext(states,nstates)
    else:
        states,nstates=generatenext(nstates,states)

    if step==N-2:
        if k%2==1:
            count=states[m-1][n][0]+states[m][n-1][1]
        else:
            count=nstates[m-1][n][0]+nstates[m][n-1][1]

print(count)