1

我们得到一个 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 解决了问题。请仅针对相同的算法帮助我。我是否必须将其转换为图表并应用一些算法。

4

1 回答 1

3

我认为你应该做一个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])

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

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

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

于 2012-10-24T20:57:33.063 回答