技术咨询：如何查找m×n矩阵中从(1,1)到(m,n)的所有可行路径？

嘿，这个问题是路径搜索里的经典基础题，咱们一步步拆解怎么找出所有可能的路径～

首先得明确：从(1,1)到(m,n)，你只能向右（列+1）或者向下（行+1）移动。那要走到终点，总共需要走 (m-1)次向下 和 (n-1)次向右 —— 所有路径其实就是这两种移动方式的不同排列组合。但如果要把每一条具体路径都列出来，就得用「遍历所有可能分支」的思路，最常用的就是回溯法。

方法一：递归回溯法（最直观好写） #

递归的思路很简单：站在当前位置，先尝试向右走（如果还没到最右列），走完这条路再退回来；然后尝试向下走（如果还没到最底行），走完再退回来。当走到终点时，就把这条路径存下来。

举个Python的实现例子：

def find_all_paths(m, n):
    paths = []
    # 递归函数：当前位置(row, col)，当前路径path
    def backtrack(row, col, path):
        # 到达终点，把当前路径加入结果
        if row == m and col == n:
            paths.append(path.copy())
            return
        # 尝试向右走：如果当前列还没到n
        if col < n:
            path.append("RIGHT")
            backtrack(row, col + 1, path)
            path.pop()  # 回溯，移除刚才加的RIGHT
        # 尝试向下走：如果当前行还没到m
        if row < m:
            path.append("DOWN")
            backtrack(row + 1, col, path)
            path.pop()  # 回溯，移除刚才加的DOWN
    # 从(1,1)开始，初始路径为空
    backtrack(1, 1, [])
    return paths

# 测试：比如3x3矩阵
print(find_all_paths(3, 3))
# 输出会是：[['RIGHT', 'RIGHT', 'DOWN', 'DOWN'], ... 其他5种路径]

这里的path.copy()很重要，因为列表是可变对象，直接加的话后续修改会影响已存的路径。

方法二：迭代式回溯（适合大矩阵，避免递归栈溢出） #

如果矩阵很大（比如m或n超过1000），递归可能会触发栈溢出，这时候可以用栈来手动模拟递归过程：

def find_all_paths_iterative(m, n):
    paths = []
    # 栈里的元素是 (当前行, 当前列, 当前路径)
    stack = [(1, 1, [])]
    while stack:
        row, col, path = stack.pop()
        if row == m and col == n:
            paths.append(path)
            continue
        # 注意：栈是后进先出，所以先压入向下的分支，再压入向右的分支，这样遍历顺序和递归一致
        if row < m:
            new_path = path.copy()
            new_path.append("DOWN")
            stack.append((row + 1, col, new_path))
        if col < n:
            new_path = path.copy()
            new_path.append("RIGHT")
            stack.append((row, col + 1, new_path))
    return paths

这样用循环代替递归，就不会有栈溢出的问题了。

额外扩展：如果矩阵有障碍怎么办？ #

如果题目加了新约束（比如某些格子不能走），只需要在尝试移动前加个判断：比如检查目标格子是否是障碍，是就跳过该方向的移动。比如修改递归里的判断：

# 假设matrix是给定的矩阵，1表示可走，0表示障碍
if col < n and matrix[row][col+1] == 1:
    # 向右走的逻辑...

内容的提问来源于stack exchange，提问作者RISHAB