Backtracking: Get maximum sum in a matrix

Problem Statement:

You are given an m*n matrix, each cell has an integer.

You need to return the path with maximum sum.

You can start at any cell and you may go L, R, up or down, but you cannot visit same cell twice.

Example

Input:
[[0,6,0],
 [5,8,7],
 [0,9,0]]

Output: 24

9 -> 8 -> 7

Solution

This problem can be solved by using backtracking/DFS.

For each cell we can do a DFS and get the maximum possible gold.

Then we return the maximum sum we got from all the starting points.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<vector>
#include<set>

using namespace std;


int helper(vector<vector<int>> &grid, int i,int j, int m, int n, vector<vector<bool>> &boolGrid)
{
  
  
  if(i<0 || j<0 || i>=m || j>=n || grid[i][j] == 0 || boolGrid[i][j]) return 0;
  
  boolGrid[i][j] = true;
  int left = helper(grid,i,j-1,m,n,boolGrid);
  int right = helper(grid,i,j+1,m,n,boolGrid);
  int up = helper(grid,i-1,j,m,n,boolGrid);
  int down = helper(grid,i+1,j,m,n,boolGrid);
  boolGrid[i][j] = false;
  
  return max(left, max(right,max(up,down))) + grid[i][j];
}

int get_maximum_gold(vector<vector<int>>& grid) 
{
  
  if(grid.size() == 0) return 0;
  
  int maxGold = 0;
  int m = grid.size();
  int n = grid[0].size();
  
  vector<vector<bool>> boolGrid(m, vector<bool>(n,false));
  
  for(int i=0;i<m;i++){
      for(int j=0;j<n;j++)
      {
          if(grid[i][j] > 0)
          {
              int gold = helper(grid,i,j,m,n,boolGrid);
              maxGold = max(maxGold,gold);
          }
      }
  }
  return maxGold;
}



int main()
{
   std::vector<vector<int>> grid =  {{0,6,0},
                                      {5,8,7},
                                      {0,9,0}};

   cout<<"Result = "<<get_maximum_gold(grid)<<endl;

    return 0;
}

Output:

Result = 24