What are the Minimum Initial Points to Reach Destination ?

  • To begin from the upper left corner of a given framework, one needs to achieve the base right corner.
  • Every cell in the grid contains a number, the number may positive or negative.
  • We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points.
  • We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :
    • From a cell (i, j) we can move to (i+1, j) or (i, j+1).
    • We cannot move from (i, j) if your overall points at (i, j) is <= 0.
    • We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.

Syntax

minInitTokens(matrix)

Sample Code in C++

#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
   {-2,-3,3},
   {-5,-10,1},
   {10,30,-5}
};

int max(int a, int b) {
   return (a>b)?a:b;
}

int minInitPoints() {
   int minToken[ROW][COL];
   int m = ROW, n = COL;
   
   minToken[m-1][n-1] = tokens[m-1][n-1] > 0? 1: abs(tokens[m-1][n-1]) + 1;
   
   for (int i = m-2; i >= 0; i--)    //from last row to first row, fill points
      minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);
   
   for (int j = n-2; j >= 0; j--)    //fill last column to first column, fill points
      minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

   for (int i=m-2; i>=0; i--) {
      for (int j=n-2; j>=0; j--) {
         int remPoint = min(minToken[i+1][j], minToken[i][j+1]);    //calculate remaining points
         minToken[i][j] = max(remPoint - tokens[i][j], 1);
      }
   }
   return minToken[0][0];
}

int main() {
   cout << "Least Points Required: " << minInitPoints();
}

Output

Least Points Required: 7

Categorized in:

Data Structure

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,