计算二进制矩阵中的所有路径

“当它只向下和向右移动两个方向”相关问题的简单部分是,路径不能自身重复。如果您允许所有四个方向,就像您当前的问题一样,您需要限制Alfie访问一个单元格的次数不得超过一次。如果没有这个限制,阿尔菲可以在两个细胞之间来回振荡,或者继续循环,从而产生无限多条路径。所以我们增加了限制:一个小区最多只能访问一次。

我们需要实施这一限制。做这件事的一个简单方法是做一秒钟 NxN visited 并定义为 visited[X][Y] 是 True False 2 为了将其与墙壁或未访问的单元格区分开来,我后来想到了这一点,但它会占用更少的内存。)

现在有多种算法可以解决这个问题。也许最简单的方法是有一个外部例程来设置,并调用一个内部递归例程来添加路径。这里是一些类似Python的伪代码,为了清晰起见,忽略了一些效率。请注意,Python中的矩阵是基于零的,因此监狱的两个角位于(0,0)和(N-1,N-1)。

def count_paths(N, prison):
    """Return the total number of unique possible paths which Alfie can
    take to escape the prison."""

    def count_paths_recurse(X, Y, prison, visited):
        """Return the number of paths starting from cell (X, Y) where
        pathcount visited[] marks the cells not to visit."""
        if X == N-1 and Y == N-1:  # reached the exit cell
            return 1
        visited[X][Y] = True
        pathcount = 0
        for direction in (right, left, down, up):
            Xnew, Ynew = neighoring cell coordinates in that direction
            if Xnew and Ynew are inside the prison
                    and prison[Xnew][Ynew] == 0
                    and not visited[Xnew][Ynew]:
                pathcount += count_paths_recurse(Xnew, Ynew, prison, visited)
        visited[X][Y] = False
        return pathcount

    if prison is not an NxN matrix containing only 0s and 1s:
        raise an error
    create visited as an NxN matrix containing only False
    if prison[0][0] != 0 or prison[N-1][N-1] != 0:
        return 0
    return count_paths_recurse(0, 0, prison, visited)

由于每个单元格的方向顺序一致(本代码中为右、左、下、上),因此每条路径都是唯一的。我已经用这个算法构建了一个完整的Python程序,它很有效,在所有三个示例中都给出了所需的答案。