矩阵中的路径数

Question

我的任务是编写一个函数，从左上到右下返回矩阵中有效路径的数量。矩阵由bool组成，其中1代表一个壁，0代表一个自由细胞。任务是找出通过空闲单元格的路径数。我写了一些代码，但不知何故不能工作。我是编程的初学者。我必须使用递归，并且使用。at()代替[]。

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

void path_counter (unsigned int n, unsigned int m, unsigned int i, 
unsigned int j, int &num, 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) { 
const unsigned int n = mat.size();
const unsigned int m = mat.at(0).size();

int num_of_paths = 0; 
int i = 0; 
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, std::vector<std::vector<bool>> mat) { 

if(i>n-1) {num+=0; } 

while (i<=n-1 && j<=m-1) { 
if ((i==n-2 && j==m-1) || (i==n-1 && j==m-2)) { 
if (mat.at(i).at(j) == 0) {num+=1; } 
} 
else if (mat.at(i+1).at(j) == 0 && mat.at(i).at(j+1) == 0) { 
path_counter(n, m, i+1, j, num, mat); 
path_counter(n, m, i, j+1, num, mat); 
} 
else if (mat.at(i+1).at(j) == 1 && mat.at(i).at(j+1) == 0) { 
path_counter(n, m, i, j+1, num, mat); 
} 
else if (mat.at(i+1).at(j) == 0 && mat.at(i).at(j+1) == 1) { 
path_counter(n, m, i+1, j, num, mat); 
} 
else if (mat.at(i+1).at(j) == 1 && mat.at(i).at(j+1) == 1) { 
num+=0; 
} 
} 
} 

Answer 1

我将放弃递归，只将路径长度累加到一个与mat大小相同的矩阵counts中:

int getCount(const std::vector<std::vector<int>>& counts, int i, int j) {
if (i < 0) {
return 0;
}
if (j < 0) {
return 0;
}
return counts[i][j];
}
int valid_paths(const std::vector<std::vector<bool>> &mat) {
int m = mat.size();
int n = mat[0].size();
std::vector<std::vector<int>> counts;
// Initialization
for (const auto& row: mat) {
counts.push_back(std::vector<int>(row.size(), 0));
}
if (mat[0][0]) {
counts[0][0] = 1;
}
int k = (m-1) + (n-1) + 1;
for (int i = 1; i < k; i++) {
int row = std::min(i, m-1);
int col = i - row;
while (row >= 0 && col < n) {
counts[row][col] = mat[row][col]?
getCount(counts, row-1, col) + getCount(counts, row, col-1) : 0;
row--;
col++;
}
}
return counts[m-1][n-1];
}