Min cost in maze traversal using recursion (please find the issue in below mention solution)

Question

Please help me in finding that where I am doing the mistake in this solution as my output is coming wrong. thanks in advance.

1. You are given a number n, representing the number of rows.
2. You are given a number m, representing the number of columns.
3. You are given n*m numbers, representing elements of 2d array a, which represents a maze.
4. You are standing in top-left cell and are required to move to bottom-right cell.
5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.
6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom- right cell).
7. You are required to traverse through the matrix and print the cost of path which is least costly.

// making the recursive call to findMinCost by reducing the row and column and finding the min cost out of that  
public static int findMinCost(int[][] maze, int row, int col) {
  if(row == 0 && col == 0) {
    return maze[row][col];
  }
   int cost = 0;
            
  if(row >= 0 && col >=0) {
   cost += Integer.min(findMinCost(maze, row-1, col),findMinCost(maze, row, col- 
    1))+maze[row][col];
   }
     return cost;
}

Answer 1

The main problem is that when one or both of the coordinates become negative (and this will happen), your function returns 0 as cost. This is not correct, as zero might be an interesting cost to go for. In this case a search is made outside the maze and that should be made impossible: so return an extreme high cost in that case, not 0.

The fix is simple: add an else block to your second if block:

} else return Integer.MAX_VALUE;

Now it will work for small mazes. (I assume you correctly call your function with row and col referencing the bottom-right cell in the maze)

For larger mazes you will run into a timing problem, since this algorithm will revisit the same sub-paths over and over again. You can solve this by using memoization.