[Python] 通路を見つける

問題

N×Nの行列があり、左端上から右端下までの通路を探す。道は1壁は0で表される。また、右が下の方向にのみ進むことができる。

例

下の行列であれば、(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)と進む。

$$ \left( \begin{array}{cccc} 1&1&0&0 \\ 0&1&1&0 \\ 0&0&1&0 \\ 0&0&1&1 \end{array} \right) $$

回答

def path_finder(maze, position, N):
    # ゴールまでに通過した道をリストにして返す。
    if position == (N-1, N-1):
        return [(N-1, N-1)]
    x, y = position
    if x + 1 < N and maze[x+1][y] == 1:
        a = path_finder(maze, (x+1, y), N)
        if a is not None:
            return [(x, y)] + a
    if y + 1 < N and maze[x][y+1] == 1:
        b = path_finder(maze, (x, y+1), N)
        if b is not None:
            return [(x, y)] + b

maze = [[1, 1, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 1, 0],
        [0, 0, 1, 1]]

print(path_finder(maze, (0, 0), 4))