网格中的机器人——如何获得所有可能的路径

Question

我试图解决这个问题：

有一个包含r行和c列的网格。坐在左上角牢房里的机器人只能向两个方向移动，右下。但某些细胞必须避免，机器人不能踩到它们。从左上角到右下角为机器人找到一条路径。

这个问题特别需要一条路径，这似乎是直截了当的：

将网格设置为布尔[][]，我得到的伪代码是

List<String> path = new ArrayList<String>()
boolean found = false

void getPath(r, c){
    if (!found) {

      if ( (r or c is outofbounds) || (!grid[r][c]) )
          return

      if (r==0 AND c==0)  // we reached
           found = true

      getPath(r-1, c)
      getPath(r, c-1)

      String cell = "(" + r + ", " + c + ")"
      path.add(cell)

    }    
}

尽管我想知道如何获得所有可能的路径（不仅是计数，还有路径值）。注意，它有r行和c列，所以它不是nxn网格。我试图想出一个DP/递归的解决方案，但却找不到任何解决方案，而且陷入了困境。很难想象递归是以两种方式进行的。

有什么建议吗？此外，对于如何“思考”此类问题的任何一般性帮助，我们都将不胜感激：）。

Answer 1

有什么建议吗？此外，对于如何“思考”此类问题的任何一般性帮助，我们都将不胜感激：）。

解决问题的方法：

1. 在头脑中构建问题的图G。在这种情况下，顶点是网格中的单元，在存在有效机器人移动的位置创建定向边

实际上，你不需要构造图，因为边的集合非常清晰，或者像通常一样进行拓扑排序，矩阵的迭代（增量行索引和增量列索引）是这种隐式图的拓扑排序。

计算后，答案存储在dp[n-1][m-1]中，n是行数，m是列数。总运行时间为O（nm）。

如何找到所有可能的有效路径：
通常的回溯是有效的，我们可以通过应用早期修剪来加速回溯。事实上，如果我们计算dp矩阵，然后从单元[n-1][m-1]进行回溯，我们可以避免机器人进入dp值为零的单元时出现无效路径。

预先计算了dp矩阵的Python代码：

n, m = 3, 4
bad = [[False, False, False, False],
       [ True,  True, False, False],
       [False, False, False, False]]
dp = [[1, 1, 1, 1], 
      [0, 0, 1, 2], 
      [0, 0, 1, 3]]

paths = []
curpath = []
def getPath(r, c):
    if dp[r][c] == 0 or r < 0 or c < 0:
        return
    curpath.append((r, c))
    if r == 0 and c == 0:
        paths.append(list(reversed(curpath)))
    getPath(r - 1, c)
    getPath(r, c - 1)
    curpath.pop()

getPath(n - 1, m - 1)
print(paths)

# valid paths are [[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)], 
#                  [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)], 
#                  [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]]

请注意，这与您的代码非常相似，需要将所有有效路径存储在一起，并注意附加列表是curpath的副本，以避免以空列表结束。