如何用Gofer函数式编程语言打印m×n矩阵的所有可行路径

嘿，这个问题在函数式编程里简直是递归的经典应用场景！Gofer作为Haskell的近亲，用它来实现这个需求特别顺手——毕竟递归和列表操作是函数式语言的强项。

核心思路 #

我们可以用递归的方式拆解问题：

• 对于矩阵中的任意位置(i,j)，到达右下角(m,n)的所有路径，等于从(i+1,j)向下走的所有路径加上从(i,j+1)向右走的所有路径
• 边界条件：
  1. 当我们已经到达右下角(i == m && j == n)时，只有一条路径（就是当前点本身）
  2. 如果当前位置超出矩阵范围(i > m || j > n)，则没有可行路径

完整代码实现 #

我们用坐标列表来表示一条路径（比如[(1,1), (1,2), (2,2)]就是从左上到右下的一条路径），具体代码如下：

-- 定义函数：paths startRow startCol totalRows totalCols -> 所有可行路径的列表
paths :: Int -> Int -> Int -> Int -> [[(Int, Int)]]
paths i j m n
    -- 到达终点，返回仅包含当前点的路径
    | i == m && j == n = [[(i, j)]]
    -- 超出矩阵范围，没有路径
    | i > m || j > n = []
    -- 递归：向下走的路径 + 向右走的路径，每条路径前加上当前坐标
    | otherwise = map ((i,j):) (paths (i+1) j m n) ++ map ((i,j):) (paths i (j+1) m n)

-- 测试示例：打印2×2矩阵的所有路径
main = print $ paths 1 1 2 2

代码解释 #

• map ((i,j):)：这个操作是把当前坐标(i,j)添加到每条子路径的开头——因为paths (i+1) j m n返回的是从(i+1,j)到终点的所有路径，我们把当前点前置，就得到了从(i,j)出发经过向下走的完整路径，向右走的逻辑同理。
• ++：Gofer里的列表拼接操作，用来把向下走的路径列表和向右走的路径列表合并成一个完整的路径集合。
• 边界条件的处理确保了递归不会无限进行，同时正确终止。

运行示例 #

比如运行上述测试代码（2×2矩阵），你会得到输出：

[[(1,1),(1,2),(2,2)],[(1,1),(2,1),(2,2)]]

这正好是2×2矩阵里的两条可行路径，完全符合预期。

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