algorithm - 矩阵中的方法数

Question

给定一个 nxn 方阵，其中包含 0 和 1。 0 表示封闭单元，1 表示机器人可以行走的开放单元。如果你的机器人最初在 (0,0) 处，有多少种方法可以到达 (n-1,n-1)。
您的机器人可以向左、向右、向上和向下移动。路径需要不同。就像如果你有一个循环那么你可以将路径计算为 1 而不是无限。例如答案7x7 矩阵。

1 1 0 1 1 0 1
0 1 0 0 1 1 1
1 1 1 1 0 1 0
0 1 0 1 1 1 1
0 1 0 0 1 0 1
0 1 1 1 1 0 1
0 0 0 0 1 1 1

是 4

4条路径是:
_ _ 0 1 1 0 1
0 _ 0 0 1 1 1
1 _ 1 1 0 1 0
0 _ 0 1 1 1 1
0 _ 0 0 1 0 1
0 _ _ _ 0 1
0 0 0 0 _ _ _

_ _ 0 1 1 0 1
0 _ 0 0 1 1 1
1 _ 1 1 0 1 0
0 _ 0 1 _ _ _
0 _ 0 0 _ 0 _
0 _ _ _ 0 _
0 0 0 0 1 1 _

_ _ 0 1 1 0 1
0 _ 0 0 1 1 1
1 _ _ _ 0 1 0
0 1 0 _ _ 1 1
0 1 0 0 _ 0 1
0 1 1 1 _ 0 1
0 0 0 0 _ _ _

_ _ 0 1 1 0 1
0 _ 0 0 1 1 1
1 _ _ _ 0 1 0
0 1 0 _ _ _ _
0 1 0 0 1 0 _
0 1 1 1 1 0 _
0 0 0 0 1 1 _

当只允许机器人向右和向下移动时，我已经使用 dp 解决了问题。请仅针对相同的算法帮助我。我是否必须将其转换为图表并应用一些算法。

Answer 1

我认为你应该做一个 DFS记住所遵循的路径。在伪代码中，它看起来像这样:

DFS(matrix, path):
   /* End conditions */
   If path.last is [n-1, n-1]
      print path /* Hooray! Found a path! */
   If path.last has already been visited in path
      Discard solution
   If path.last is out of bounds (coordinates < 0 or > n-1)
      Discard solution
   If matrix[path.last] value is 0
      Discard solution

   /* We're in the middle of a path: continue exploring */
   For direction in [1, 0], [0, 1], [-1, 0], [0, -1]
      Add [path.last + direction] to path // Move north, south, east, west
      DFS(matrix, path)
      Remove last element from path

/* Call the algorithm */
DFS(matrix, [1, 1])

在此算法中，您可以传递对矩阵和路径的引用，这为您提供了一种常量内存算法(您只有一个 path 的实例)。至于时间复杂度，这在可能路径的数量上是线性的(因为你探索每条可能的路径一次，甚至是被忽略的路径)，并且在它们的长度上是二次的(因为你测试，对于每个点，如果它已经存在于线性搜索的路径中)。请记住，路径数量可以呈指数增长 n ，并且路径的长度在最坏情况下为 n^2 .非常慢的蛮力算法。

此算法的最坏情况将是一个仅由具有指数复杂度的矩阵填充的矩阵。

最好的情况 是一个矩阵，在 [1, 1] 之间只有一条可能的路径。和 [n-1, n-1] .在这种情况下，路径的长度很复杂，可能在 O(n) 之间。和 O(n^2) .