打印二维矩阵左上到右下所有1构成的可行路径（附问题代码）

给定M行N列的二维矩阵，初始位置为矩阵左上角单元格(0,0)，每次仅允许向右（R）或向下（D）移动。矩阵元素由1和0构成：

• 值为1代表该单元格可通行
• 值为0代表该单元格不可通行
  需要打印所有从左上角(0,0)到右下角(M-1,N-1)的可行路径，输出格式示例：[[R,R,D,D], [R,D,D,R], [D,D,R,R]]

给出的原有实现代码如下：

def traverse(grid, rows, cols, i, j, result, path, element):
    if i==rows-1 and j==cols-1:
        result.append(path)
        print(result)
        path = []
        return
    if i>=rows or j>=cols or grid[i][j]==0:
        path = []
        return
    if grid[i][j] == 1 and element != 'x':
        path.append(element)
    traverse(grid, rows, cols, i, j+1, result, path, 'r')
    traverse(grid, rows, cols, i+1, j, result, path, 'd')

grid = [[1,1,1],[0,1,1],[1,1,1]]
rows = len(grid)
cols = len(grid[0])
traverse(grid, rows, cols, 0, 0, [], [], 'x')

• 路径列表为引用传递，递归过程中所有分支共享同一份path数据，没有回溯撤销操作，不同路径的移动步骤会互相污染
• 判断逻辑顺序错误：先判断是否到达终点，再追加当前步的移动方向，导致存入结果的路径永远缺少最后一步
• 存入结果时直接追加path原对象，没有创建副本，后续对path的修改会同步改动已经存入结果的路径内容
• 越界/撞障碍时给局部变量path赋值空列表的操作无效，不会影响上层递归的path数据
• 移动方向使用小写r/d，不符合题目要求的大写R/D格式

采用标准回溯框架实现，修复上述所有问题：

def find_all_paths(grid):
    rows = len(grid)
    cols = len(grid[0])
    result = []
    # 起点或终点不可通行直接返回空结果
    if grid[0][0] == 0 or grid[-1][-1] == 0:
        return result

    def backtrack(i, j, path):
        # 越界或当前单元格不可通行，直接返回
        if i >= rows or j >= cols or grid[i][j] == 0:
            return
        # 到达终点，存入当前路径的副本
        if i == rows - 1 and j == cols - 1:
            result.append(path.copy())
            return
        # 尝试向右移动
        path.append('R')
        backtrack(i, j + 1, path)
        path.pop()  # 回溯撤销选择
        # 尝试向下移动
        path.append('D')
        backtrack(i + 1, j, path)
        path.pop()  # 回溯撤销选择

    backtrack(0, 0, [])
    return result

# 测试用例
grid = [[1,1,1],[0,1,1],[1,1,1]]
print(find_all_paths(grid))

针对给出的测试矩阵，运行输出为：[['R', 'R', 'D', 'D'], ['R', 'D', 'R', 'D'], ['R', 'D', 'D', 'R']]，符合题目输出要求。

内容的提问来源于stack exchange，提问作者usercode-123