计算二进制矩阵中的所有路径 [英] Count all path in a binary matrix
问题描述
NxN的矩阵有0和1，
0表示他可以通过这个单元格，1表示它被阻塞。如果他的当前位置是（X，Y），他可以移动到（X + 1，Y），（X-1，Y），（X， Y + 1），（X，Y-1）}。
如果第一个单元格（1,1）和最后一个单元格（N，N）包含'1'，那么他不能从矩阵中分离出来。
他想知道他为逃避监狱所能采取的唯一可能路径的总数。最初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
我知道如何解决它只能向下移动两个方向正确。
但是当它向四个方向移动时，如何处理这样的问题..？
关于相关问题的简单部分当它只向下移动两个方向时，路径不能翻倍本身。如果你允许所有四个方向，就像在你当前的问题中一样，你需要限制Alfie可能不止一次访问一个单元格。没有这种限制，Alfie可能会在两个单元格之间来回摆动，或者继续前进一圈，导致无限多的路径。所以我们增加了这个限制：一个单元最多可以访问一次。
我们需要强制执行这个限制。一个简单的方法是制作第二个 现在有多种算法可以解决这个问题。也许最简单的方法是创建一个外部例程来设置事件并调用内部递归例程来添加路径。这是一些类似Python的伪代码，为了清晰起见，忽略了一些效率。请注意，Python中的矩阵是基于零的，所以监狱的两个角落处于（0,0）和（N-1，N-1）。 由于每个单元格的方向都是按照一致的顺序（这个代码中的右边，左边，下边），每条路径都是唯一的。我已经从这个算法中构建了一个完整的Python程序，它可以工作，在所有三个示例中给出所需的答案。 A matrix of NxN has either 0 and 1. he wants to know the total number of unique possible paths which he can take to escape the prison.Initially Alfie is in cell (1,1) while the exit of the cell (N,N). Example : Input : Input : I know how to solve when it moves only two direction down and right. The easy part about the related problem "when it moves only two direction down and right" is that the path cannot double back on itself. If you allow all four directions, as in your current problem, you need the restriction that Alfie may not visit a cell more than once. Without that restriction, Alfie could oscillate back and forth between two cells, or keep going in a circle, causing infinitely many paths. So we add that restriction: a cell may be visited at most once. We need to enforce that restriction. An easy way to do this is to make a second There are multiple algorithms that can now solve the problem. Perhaps the easiest way is to have an outer routine that sets things up and call an inner recursive routine to add up the paths. Here is some Python-like pseudocode, ignoring some efficiencies for the sake of clarity. Note that matrices in Python are zero-based, so the two corners of the prison are at (0,0) and (N-1, N-1). Since the directions from each cell are in a consistent order (right, left, down, up in this code), each path will be unique. I have build a full Python program from this algorithm, and it works, giving the desired answers in all three examples. 这篇关于计算二进制矩阵中的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ NxN 矩阵，但这个矩阵只使用布尔值。我们可以称它为 visited ，并通过 visited [X] [Y] 来定义它 True 当且仅当Alfie在当前路径中访问该单元格时;否则它是 False 。 （另一种方法是使用 2 标记访问过的单元格，以便将它与墙面或未访问过的单元格区分开来 - 我后面想到了这一点，但它会使用更少的内存。 ）
def count_paths（N，监狱）：
返回Alfie可以花
逃过监狱的唯一可能路径的总数。
def count_paths_recurse（X，Y，监狱，visited）：
返回从单元格（X，Y）开始的路径数，其中
pathcount visited []标记单元格
如果X == N-1和Y == N-1：＃到达退出单元
返回1
visited [X] [Y] = True
pathcount = 0
用于（右，左，下，上）方向：
Xnew，Ynew =在该方向上的neighoring单元坐标
如果Xnew和Ynew在监狱内
和监狱[Xnew] [Ynew] == 0
并且未被访问[Xnew] [Ynew]：
pathcount + = count_paths_recurse（Xnew，Ynew，prison，如果监狱不是只包含0和1的N×N矩阵：
提出错误
visited [X] [Y] = False
return pathcount
$如果监狱[0] [0]！= 0或监狱[N-1] [N-1]！= 0：
返回0 $，b $ b create被视为仅包含False
的NxN矩阵b $ b return count_paths_recurse（0，0，prison，visited）
0 means he can pass through this cell and 1 means it is blocked.
he can move in all four direction{ if his current location is (X,Y), he can move to either (X+1,Y), (X−1,Y), (X,Y+1), (X,Y−1) }.
If the first cell (1,1) and the last cell(N,N) contain '1' ,then he can't break out of the matrix.
Input
4
0 1 1 0
0 0 1 0
0 0 0 0
0 1 1 0
Output:
2
4
0 0 0 1
0 0 0 0
1 1 1 0
1 0 0 0
Output:
4
4
0 1 1 0
0 0 1 1
0 0 0 0
0 1 0 0
Output:
4
But how to approach problem like this when it moves in four direction..? NxN matrix, but this one using only Boolean values. We can call it visited and define it by visited[X][Y] is True if and only if Alfie has visited that cell during the current path; otherwise it is False. (Another way is to mark a visited cell with a 2 to distinguish it from a wall or non-visited cell--I thought of this later but it would use less memory.)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)
