dimanche 10 octobre 2021

C++ dynamic programming grid traversal

I want to create a recursive function to calculate the number of ways to traverse a grid (i.e. to go from the upper left to the bottom right by moving only downward or to the right. I want to store the values in a matrix M, i.e. M[n][m] should be the number of ways to traverse a grid of size nm. I tried the following code, however it does not return anything. The compiler doesn't indicate any error, it simply does nothing. What's wrong with my code?

#include<iostream>
#include<vector>
using matrix = std::vector<std::vector<int>>;
int gridTraveler(const int& n, const int& m, matrix& M){
    if (m==0||n==0){
        M[0][0]=0;
        return 0;
    } else if (m==1||n==1){
        M[n][m]=1;
        return 1;
    } else {
        M[n][m]= gridTraveler(n-1,m,M)+gridTraveler(n,m-1,M);
        return M[n][m];
    }
}

int main(){
    matrix M;
    int n=2, m=0;
    std::cout<< gridTraveler(n,m,M) <<std::endl;
}

Aucun commentaire:

Enregistrer un commentaire