गंतव्य तक पहुंचने के लिए न्यूनतम प्रारंभिक पॉइंट्स

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

कुछ नियम हैं:

हम केवल दाएं या नीचे जा सकते हैं।
हम सेल (i, j) पर नहीं जा सकते यदि हमारे कुल टोकन उस सेल के मान से कम हैं।
हमें न्यूनतम धनात्मक पॉइंट्स के साथ गंतव्य तक पहुंचना है।

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

इनपुट: प्रत्येक कमरे के टोकन मैट्रिक्स के रूप में
-2 -3 3
-5 -10 1
10 30 -5

आउटपुट: यात्रा शुरू करने के लिए आवश्यक न्यूनतम टोकन। इस उदाहरण के लिए, आवश्यक टोकन 7 है।

एल्गोरिदम

minInitTokens(matrix)

इनपुट: प्रत्येक कमरे के लिए टोकन मैट्रिक्स
आउटपुट: प्रारंभ बिंदु से गंतव्य तक पहुंचने के लिए न्यूनतम टोकन

शुरुआत
    matrix के आकार जितना minToken मैट्रिक्स परिभाषित करें
    m := matrix में पंक्तियों की संख्या
    n := matrix में कॉलम की संख्या
    यदि matrix[m-1, n-1] > 0, तो
        minToken[m-1, n-1] := 0
    अन्यथा
        minToken[m-1, n-1] := 1 + matrix[m-1, n-1] का निरपेक्ष मान
    i := m-2 से 0 तक नीचे, करें
        minToken[i, n-1] := 1 और (minToken[i+1, n-1] - matrix[i,n-1]) का अधिकतम
    पूर्ण
    j := n-2 से 0 तक नीचे, करें
        minToken[m-1, j] := 1 और (minToken[m-1, j+1] - matrix[m-1, j]) का अधिकतम
    पूर्ण
    i := m-2 से 0 तक नीचे, करें
        j := n-2 से 0 तक नीचे, करें
            rem := minToken[i+1, j] और minToken[i, j+1] का न्यूनतम
            minToken[i, j] := 1 और (rem - matrix[i,j]) का अधिकतम
        पूर्ण
    पूर्ण
    वापस minToken[0, 0]
अंत

उदाहरण (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--)
        minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);
    
    for (int j = n-2; j >= 0; j--)
        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]);
            minToken[i][j] = max(remPoint - tokens[i][j], 1);
        }
    }
    return minToken[0][0];
}

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

आउटपुट

Minimum Points Required: 7