矩阵有效路径数量计算：递归实现代码问题排查

原代码存在的问题 #

• 不必要的while循环：递归本身负责路径的逐步探索，循环会导致无限递归或计数错误
• 越界访问：当i已是最后一行（n-1）时，访问mat.at(i+1).at(j)会触发非法内存访问
• 错误的基准条件：未正确处理到达终点、遇到墙体或当前位置越界的情况
• 矩阵按值传递：每次递归都会复制整个矩阵，效率极低且无必要
• 缺失空矩阵检查：若输入矩阵为空，mat.at(0)会直接抛出异常

修正后的代码 #

#include "valid_path.h" 
#include <vector> 

void path_counter(unsigned int n, unsigned int m, unsigned int i,
unsigned int j, int &num, const std::vector<std::vector<bool>> &mat); 

// PRE: -
// POST: Returns the number of valid paths through mat starting at (0, 0).
//       Valid paths can only move right or down.  
int valid_paths(const std::vector<std::vector<bool>> &mat) { 
    // 处理空矩阵情况
    if (mat.empty() || mat.at(0).empty()) {
        return 0;
    }
    
    const unsigned int n = mat.size();
    const unsigned int m = mat.at(0).size();
    
    int num_of_paths = 0; 
    unsigned int i = 0; 
    unsigned int j = 0; 
    
    path_counter(n, m, i, j, num_of_paths, mat); 
    
    return num_of_paths; 
} 


void path_counter(unsigned int n, unsigned int m, unsigned int i,
unsigned int j, int &num, const std::vector<std::vector<bool>> &mat) { 
    // 基准条件1：当前位置越界，直接返回
    if (i >= n || j >= m) {
        return;
    }
    
    // 基准条件2：当前位置是墙体，路径无效
    if (mat.at(i).at(j)) { // bool类型中1为true（墙体），0为false（可通行）
        return;
    }
    
    // 基准条件3：到达终点，路径有效，计数+1
    if (i == n - 1 && j == m - 1) {
        num++;
        return;
    }
    
    // 递归探索向下走的路径
    path_counter(n, m, i + 1, j, num, mat);
    // 递归探索向右走的路径
    path_counter(n, m, i, j + 1, num, mat);
} 

代码解释 #

1. 空矩阵检查：在入口函数中先判断矩阵是否为空，避免后续越界访问
2. 基准条件处理：
   • 若当前位置超出矩阵范围，直接返回（路径无效）
   • 若当前位置是墙体，直接返回（路径无效）
   • 若到达右下角终点，计数加1（找到一条有效路径）
3. 递归逻辑：从当前位置分别探索向下和向右的路径，所有递归调用会自动处理后续的有效性判断
4. const引用传递矩阵：避免不必要的矩阵复制，同时保证矩阵内容不会被修改
5. 类型一致性：将起始坐标i和j改为unsigned int，与矩阵尺寸类型保持一致

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