You need to enable JavaScript to run this app. C++矩阵路径求解代码中findPaths函数为何打印path后递减i、j?
优惠活动
大模型
产品
解决方案
定价
更多

C++矩阵路径求解代码中findPaths函数为何打印path后递减i、j?

3×3矩阵路径搜索中坐标回退(i/j递减)的技术原理

你观察到的“打印完路径后i、j出现递减”的现象,是深度优先递归搜索配合回溯逻辑的正常运行表现,不是代码bug。

核心本质:递归栈帧的压入与弹出

常规实现的findPaths递归逻辑如下,所有坐标变化都是围绕栈帧生命周期展开的:

// 输入参数:当前所在坐标(i,j),全局共享的路径存储vector
void findPaths(int i, int j, vector<pair<int,int>>& path) {
    // 当前坐标存入路径
    path.push_back({i, j});

    // 递归终止:到达右下角终点
    if (i == 2 && j == 2) {
        printPath(path);
        path.pop_back(); // 弹出终点坐标,准备回溯
        return;
    }

    // 优先尝试向右移动
    if (isvalid(i, j+1)) {
        findPaths(i, j+1, path);
    }
    // 再尝试向下移动
    if (isvalid(i+1, j)) {
        findPaths(i+1, j, path);
    }

    // 当前坐标所有可走方向都遍历完成,弹出坐标准备回溯
    path.pop_back();
}
  • 递归调用的内存模型是独立栈帧:每次调用findPaths(i, j+1)时,程序会在栈上创建一个新的函数执行上下文,这个上下文里的i、j参数是独立于外层栈帧的,不会修改外层的变量值。
  • 当深层递归的任务执行完成(比如走到终点打印完路径),函数就会执行return,释放当前栈帧,程序的执行点就会回到上一层的调用位置,这时候拿到的当前活跃坐标,就是上一层栈帧里保存的原始i、j值。

坐标“递减”的具体发生过程

举一条典型路径的遍历过程,就能直观看到坐标变化的逻辑:

  1. 从起点(0,0)出发,一路向右走到(0,2),再一路向下走到(2,2),打印完这条合法路径
  2. (2,2)的栈帧执行return,程序回到上一层的(2,1)栈帧——此时当前坐标从(2,2)变回(2,1),j值从2降到1,这是你观察到的第一次“j递减”
  3. (2,1)的栈帧尝试完所有合法方向(向右到终点、向下越界),执行return回到上一层的(1,1)栈帧——此时坐标从(2,1)变回(1,1),i值从2降到1,这就是你看到的“i递减”

常见认知误区:很多人误以为i、j是全局变量被手动修改,才会出现递减。实际上i、j只是每个栈帧的局部参数,根本不存在“被某个代码块写小”的过程——所谓的递减,只是程序逐层从深层递归返回时,当前上下文切换回上层栈帧的参数值带来的视觉效果。

和路径vector的同步关系

你在代码里对path vector的push、pop操作,和栈帧的压入、弹出是完全对齐的:

  • 每压入一层新栈帧,就往path里push当前坐标
  • 每弹出一层栈帧(return回溯),就从path里pop对应坐标
    如果出现pop时机不对(比如在递归终止时忘了pop、在函数末尾忘了pop),就会导致path的长度和栈帧深度不匹配,很多人会把这种路径错乱的问题,误判为“i、j变量莫名递减”。

内容的提问来源于stack exchange,提问作者fadao838

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 22:45:08