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

Question

我正在尝试解决这个问题：

There is a grid with with r rows and c columns. A robot sitting in top left cell can only move in 2 directions, right and down. But certain cells have to be avoided and the robot cannot step on them. Find a path for the robot from the top left to the bottom right.

这个问题特别要求一条路径，这看起来很简单：

网格为boolean[][]，我的伪代码是

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/recursive 解决方案，但无法想出任何解决方案并卡住了。当递归以两种方式进行时，很难想到。

有什么指点吗？以及任何关于如何“思考”此类问题的一般帮助将不胜感激:)。

Answer 1

Any pointers? And also any general help on how to "think" about such problems would be appreciated :).

问题处理方法：

构思图 G 题。在这种情况下，顶点是网格中的单元格，并且在存在有效机器人移动的地方创建有向边。
搜索 G 的属性。在这种情况下，G 是 DAG（有向无环图）。
利用这样的属性想出一个解决办法。在这种情况下（G 是 DAG）通常使用 拓扑排序 和 动态规划 来查找有效路径的数量。

实际上你不需要构造图，因为边的集合很清楚，也不需要做拓扑排序，因为矩阵的通常迭代（增量行索引和增量列索引）是这种隐式的拓扑排序图。

动态规划部分可以通过在每个单元格 [x][y] 中存储从 [0][0] 到 [x][y] 的有效路径数量并检查下一步移动的位置来解决。
重复：

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

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

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

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 的副本，以避免以空列表结束。

运行时：O((n + m) * (amount of valid paths)) 因为模拟机器人移动属于有效路径或第一步进入使用前瞻检测到的无效路径 (dp)。警告：此方法是指数级的，因为有效路径的数量可以是 .

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

Robot in a Grid - how to get all possible paths

recursion

dynamic-programming