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

Question

NxN 的矩阵有 0 和 1。
0 表示他可以通过此单元格，1 表示它被阻止。
他可以在所有四个方向上移动{如果他的当前位置是(X，Y)，他可以移动到(X + 1，Y)，(X−1，Y)，(X，Y + 1)，(X ,Y−1)}。
如果第一个单元格(1,1)和最后一个单元格(N,N)都包含'1'，那么他就不能跳出矩阵。

他想知道他可以用来逃离 jail 的唯一可能路径的总数。最初，Alfie 在牢房 (1,1) 中，而在牢房 (N,N) 导出。

例子:
输入
4
0 1 1 0
0 0 1 0
0 0 0 0
0 1 1 0
输出:
2

输入:
4
0 0 0 1
0 0 0 0
1 1 1 0
1 0 0 0
输出:
4

输入:
4
0 1 1 0
0 0 1 1
0 0 0 0
0 1 0 0
输出:
4

当它只向下和向右移动两个方向时，我知道如何解决。
但是当它向四个方向移动时如何解决这样的问题..？

Answer 1

“当它只向右下和向右两个方向移动时”相关问题的简单部分是路径不能折回自身。如果您允许所有四个方向，就像您当前的问题一样，您需要限制 Alfie 不能多次访问一个单元格。没有这个限制，阿尔菲可以在两个细胞之间来回摆动，或者继续绕圈，从而产生无限多条路径。所以我们添加了这个限制:一个单元格最多只能被访问一次。

我们需要强制执行该限制。一种简单的方法是制作第二个 NxN 矩阵，但这个矩阵仅使用 bool 值。我们可以称它为 visited 并通过 visited[X][Y] 定义为 True 当且仅当 Alfie 在当前路径；否则为 False。 (另一种方法是用 2 标记已访问的单元格，以将其与墙壁或未访问的单元格区分开来——我后来想到了这一点，但它会占用更少的内存。)

现在有多种算法可以解决这个问题。也许最简单的方法是有一个外部例程来设置事物并调用内部递归例程来添加路径。这是一些类似 Python 的伪代码，为了清楚起见忽略了一些效率。请注意，Python 中的矩阵是从零开始的，因此 jail 的两个角位于 (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 程序，它运行良好，在所有三个示例中都给出了所需的答案。