递归数字矩阵路径查找算法问题排查与优化咨询

问题背景 #

尝试实现递归遍历数字矩阵，寻找从左上角(0,0)到右下角、路径和大于0的路径，但测试用例结果异常：首个测试用例角落箭头错误，其余测试用例完全失效。以下是问题代码及测试用例：

问题代码 #

void path_finder(std::vector<std::vector<int>> & in, std::vector<std::vector<char>> & out, bool & routeFound, int & sum, char dir = 'v', int row = 0, int col = 0) {
    if (row >= in.size() || row < 0 || col >= in[row].size() || col < 0 || out[row][col] != '-' || routeFound) {
        return;
    } 

    if (row == in.size() -1 && col == in[row].size() - 1) {
        if (sum > 0) {
            routeFound = true;
            out[row][col] = 'X';
            return;
        } 
        return;
    }

    out[row][col] = dir;
    sum += in[row][col];

    path_finder(in, out, routeFound, sum += in[row][col], 'v', row+1, col);
    path_finder(in, out, routeFound, sum += in[row][col], '>', row, col+1);
    path_finder(in, out, routeFound, sum += in[row][col], '^', row-1, col);
    path_finder(in, out, routeFound, sum += in[row][col], '<', row, col-1);
}

测试用例1 #

输入矩阵：

1 -10 1 -5 2
2 3 -20 2 1
-13 1 2 3 5
1 1 5 -4 4

预期输出：

v----
v----
v-->v
>>>^X

实际错误输出：

v----
v----
v--^>
v>>>X

测试用例2 #

输入矩阵：

1 1 1 -5 -5 
-6 -3 -5 0 4
-5 1 2 4 0
1 0 -5 0 -4

预期输出：

> v - - -
- v - > v
- v > ^ v
- > ^ - X

实际错误输出：

v^><^
v^<v^
v<v^>
v>>>- 

核心问题分析 #

1. sum多次累加与引用干扰

   • 递归调用时重复执行sum += in[row][col]，导致同一单元格值被多次计入sum；同时sum为引用传递，不同递归分支会互相修改sum值，完全破坏路径和计算逻辑。

2. 缺失回溯逻辑

   • 修改out[row][col]和sum后，未在递归返回时恢复初始状态（如将out改回'-'、sum减去当前单元格值），错误的路径标记残留会干扰后续分支遍历。

3. 终点sum计算遗漏

   • 到达终点时，sum未包含终点单元格数值就进行判断，路径和计算少了关键的最后一步。

4. 起点方向强制错误

   • 起点(0,0)默认方向被设为'v'，若最优路径为向右，起点标记会与实际路径不符。

修复后的代码 #

#include <vector>

void path_finder(std::vector<std::vector<int>> & in, std::vector<std::vector<char>> & out, bool & routeFound, int sum, char dir = ' ', int row = 0, int col = 0) {
    // 边界、已访问、已找到路径时直接返回
    if (row >= in.size() || row < 0 || col >= in[row].size() || col < 0 || out[row][col] != '-' || routeFound) {
        return;
    } 

    // 累加当前单元格值到路径和
    int current_sum = sum + in[row][col];

    // 到达终点判断：必须包含当前单元格值
    if (row == in.size() - 1 && col == in[row].size() - 1) {
        if (current_sum > 0) {
            routeFound = true;
            out[row][col] = 'X';
        }
        return;
    }

    // 标记当前路径方向（起点特殊处理，避免强制初始方向）
    if (!(row == 0 && col == 0)) {
        out[row][col] = dir;
    }

    // 递归探索四个方向，传递独立的current_sum（值传递避免分支干扰）
    path_finder(in, out, routeFound, current_sum, 'v', row+1, col);
    if (!routeFound) path_finder(in, out, routeFound, current_sum, '>', row, col+1);
    if (!routeFound) path_finder(in, out, routeFound, current_sum, '^', row-1, col);
    if (!routeFound) path_finder(in, out, routeFound, current_sum, '<', row, col-1);

    // 回溯：当前分支未找到有效路径，恢复out标记
    if (!routeFound && !(row == 0 && col == 0)) {
        out[row][col] = '-';
    }
}

// 调用示例：
// std::vector<std::vector<char>> out(rows, std::vector<char>(cols, '-'));
// bool found = false;
// path_finder(in, out, found, 0);
// // 找到路径后补全起点标记
// if (found) {
//     if (out[0][1] == '^') out[0][0] = '>';
//     else if (out[1][0] == 'v') out[0][0] = 'v';
// }

修复说明 #

1. sum改为值传递：每个递归分支使用独立的current_sum，避免不同分支互相干扰，同时不再重复累加同一单元格值。
2. 添加回溯逻辑：递归返回后，若当前分支未找到有效路径，将out[row][col]恢复为'-'，保证后续分支遍历不受影响。
3. 修正终点判断：将终点单元格值加入sum后再判断是否大于0，确保路径和计算正确。
4. 优化起点处理：起点不强制设置方向，找到路径后根据下一个单元格的方向反推起点箭头，避免初始方向错误。
5. 提前剪枝：若某方向已找到有效路径，后续方向不再探索，提升效率。

递归多方向追踪思路 #

1. 回溯法核心：每次递归前修改状态（标记路径、计算当前和），递归返回后恢复状态，确保每个分支独立性，这是多方向路径问题的基础。
2. 状态传递选择：路径和优先使用值传递，避免引用带来的状态污染；若必须用引用，需手动在递归前后恢复sum值。
3. 剪枝优化：若当前路径和加上矩阵剩余单元格的最大可能值仍无法大于0，提前终止该分支，减少无效递归。
4. 终点逻辑独立：单独处理终点判断，确保终点数值被计入路径和，且标记为'X'。
5. 起点特殊处理：起点无前置方向，需根据找到的路径第一步反推起点箭头标记。

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