गंतव्य तक पहुंचने के लिए न्यूनतम प्रारंभिक बिंदु

किसी दिए गए ग्रिड के ऊपरी-बाएँ कोने से शुरू करने के लिए, किसी को नीचे-दाएँ कोने तक पहुँचना होगा। ग्रिड में प्रत्येक सेल में एक संख्या होती है, संख्या सकारात्मक या नकारात्मक हो सकती है। जब व्यक्ति किसी सेल (i, j) में पहुंचता है तो उसके पास मौजूद टोकन की संख्या उस सेल के मूल्यों के साथ बढ़ाई या घटाई जा सकती है। हमें यात्रा को पूरा करने के लिए न्यूनतम प्रारंभिक टोकन की आवश्यकता है।

कुछ नियम हैं -

• हम या तो दाईं ओर या नीचे जा सकते हैं।
• यदि हमारा कुल टोकन (i, j) के मान से कम है, तो हम सेल (i, j) में नहीं जा सकते।
• हमें न्यूनतम सकारात्मक बिंदुओं के साथ गंतव्य तक पहुंचना है।

इनपुट और आउटपुट

Input:
The token for each room as a matrix.
-2  -3  3
-5 -10  1
10  30 -5

Output:
The minimum token required to start the journey. For this example, the required token is 7.

एल्गोरिदम

minInitTokens(matrix)

इनपुट: प्रत्येक कमरे के लिए टोकन मैट्रिक्स।

आउटपुट - गंतव्य के प्रारंभ बिंदु तक पहुंचने के लिए आवश्यक न्यूनतम टोकन।

Begin
   define matrix minToken of size same as matrix
   m := number of rows in matrix
   n := number of columns in matrix

   if matrix[m-1, n-1] > 0, then
      minToken[m-1, n-1] := 0
   else
      minToken[m-1, n-1] := 1 + absolute value of matrix[m-1, n-1]

   for i := m-2 down to 0, do
      minToken[i, n-1] := maximum of 1 and (minToken[i+1, n-1]-matrix[i,n-1])
   done

   for j := n-2 down to 0, do
      minToken[m-1, j] := maximum of 1 and (minToken[m-1, j+1]-matrix[m-1, j])
   done

   for i := m-2 down to 0, do
      for j := n-2 down to 0, do
         rem := minimum of minToken[i+1, j] and minToken[i, j+1]
         minPoint[i, j] := maximum of 1 and (rem – matrix[i,j])
      done
   done

   return minToken[0, 0]
End

उदाहरण

#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 << "Minimum Points Required: " << minInitPoints();
}

आउटपुट

Minimum Points Required: 7