Why does the following code returns wrong value of count?

Question

Problem: Given a 2D matrix of n x m. The matrix contained integers. Given a destination position, find the number of ways in which that person can reach the destination from source(origin) fulfilling the following conditions- (i) Movement can be only in north, south, east or west direction. (ii) A person can move from one cell to other if and only if that cell has value less than the value in the current cell.

#include<iostream>
using namespace std;
void printSolution(int** solution, int n, int m)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout<<solution[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
    int count = 0;
    if(x==desx-1 && y==desy-1)
    {
        solution[x][y] = 1;
        printSolution(solution, n, m);
        count++;
        solution[x][y]=0;
        //cout<<"Return 1"<<endl;
        return count;

    }
    if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
    {
        //cout<<"Return 2"<<endl;
        return count;   
    }
    solution[x][y] = 1;
    if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
    {
        count = mazeHelp(maze, solution, x+1, y, desx, desy, n, m); 
    }
    if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
    {
        count = mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
    }
    if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
    {
        count = mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
    }
    if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
    {
        count = mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
    }
    solution[x][y] = 0;
}
int printPaths(int** maze, int desx, int desy, int** solution, int n, int m)
{
    int count = 0;
    count = mazeHelp(maze, solution, 0, 0, desx, desy, n, m);
    return count;
}

int main()
{
    int desx, desy, n, m;
    cout<<"Enter number of rows : ";
    cin>>n;
    cout<<"Enter number of columns : ";
    cin>>m;
    cout<<"Enter matrix : "<<endl;
    int** solution = new int*[n];
  for(int i=0;i<n;i++){
    solution[i] = new int[m];
  }
    int** maze = new int*[m];
    for(int i=0;i<n;i++){
    maze[i] = new int[m];
  }
  for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>maze[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0;j<m;j++)
        {
            solution[i][j] = 0;
        }
    }
    cout<<"Enter destination address (x,y) : ";
    cin>>desx>>desy;
    int res = printPaths(maze, desx, desy, solution, n, m);
    cout<<"Total number of paths : "<<res;
    return 0;
}

My code prints correct paths for every input but return wrong value of count every time. Is there any error in calculating the number of paths?

The most obvious problem is that you don't always return a count from the mazeHelp function. Another problem is that you should add the count, not assign the count when you call recursively. I.e. count += mazeHelp(...); — john

RobertBaron RobertBaron · Accepted Answer · 2019-07-20T20:56:09

As already mentioned in the comments, in the mazeHelp function, you recursively call mazeHelp at several places. Each call returns a number of found paths. You have to cumulate them in the count variable, and return that count at the end, for parent recursive calls.

int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
    int count = 0;
    if(x==desx-1 && y==desy-1)
    {
        solution[x][y] = 1;
        printSolution(solution, n, m);
        count++;
        solution[x][y]=0;
        //cout<<"Return 1"<<endl;
        return count;

    }
    if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
    {
        //cout<<"Return 2"<<endl;
        return count;   
    }
    solution[x][y] = 1;
    if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
    {
        count += mazeHelp(maze, solution, x+1, y, desx, desy, n, m); 
    }
    if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
    {
        count += mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
    }
    if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
    {
        count += mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
    }
    if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
    {
        count += mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
    }
    solution[x][y] = 0;
    return count;
}

Why does the following code returns wrong value of count?

1 Answers