दो ट्रैवर्सल का उपयोग करके ग्रिड में अधिकतम पॉइंट्स एकत्र करना

एक मैट्रिक्स दिया गया है जिसमें प्रत्येक सेल में पॉइंट्स होते हैं। दो ट्रैवर्सल का उपयोग करके इस ग्रिड से अधिकतम पॉइंट्स कैसे प्राप्त करें।

शर्तें

• पहला ट्रैवर्सल ग्रिड के ऊपरी बाएं सेल से शुरू होकर निचले बाएं कोने तक जाता है। दूसरा ट्रैवर्सल ऊपरी दाएं कोने से शुरू होकर निचले दाएं कोने तक जाता है।
• एक सेल से हम केवल नीचे, नीचे-बाएं या नीचे-दाएं सेल में जा सकते हैं।
• यदि एक ट्रैवर्सल किसी सेल से पॉइंट्स ले चुका है, तो अगले ट्रैवर्सल को उस सेल से कोई पॉइंट नहीं मिलेगा।

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

इनपुट: पॉइंट्स वाला एक ग्रिड
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10

आउटपुट: दो ट्रैवर्सल द्वारा एकत्र अधिकतम पॉइंट्स = 73
पहला ट्रैवर्सल: 3 + 2 + 20 + 1 + 1 = 27
दूसरा ट्रैवर्सल: 2 + 4 + 10 + 20 + 10 = 46

एल्गोरिदम

findMaxVal(mTable, x, y1, y2)

इनपुट: एक 3D मेमोराइजेशन टेबल, x मान और y1, y2
आउटपुट: अधिकतम मान

शुरुआत
    यदि x, y1 और y2 वैध नहीं हैं, तो
        वापस -∞
    यदि दोनों ट्रैवर्सल पूरे हो गए हैं, तो
        यदि y1 = y2, तो
            वापस grid[x, y1]
        अन्यथा
            वापस grid[x, y1] + grid[x, y2]
    यदि दोनों ट्रैवर्सल अंतिम पंक्ति पर हैं, तो
        वापस -∞
    यदि सबप्रॉब्लम हल हो चुका है, तो
        वापस mTable[x, y1, y2]
    res := -∞ सेट करें
    यदि y1 = y2, तो
        temp := grid[x, y1]
    अन्यथा
        temp := grid[x, y1] + grid[x, y2]
    res := res और (temp + findMaxVal(mTable, x+1, y1, y2-1)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1, y2+1)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1, y2)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1-1, y2)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1-1, y2-1)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1+1, y2)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1+1, y2-1)) का अधिकतम
    res := res और (temp + findMaxVal(mTable, x+1, y1+1, y2+1)) का अधिकतम
    mTable[x, y1, y2] = res सेट करके वापस करें
अंत

उदाहरण (C++ कोड)

#include <iostream>
#define ROW 5
#define COL 4
using namespace std;

int grid[ROW][COL] = {
    {3, 6, 8, 2},
    {5, 2, 4, 3},
    {1, 1, 20, 10},
    {1, 1, 20, 10},
    {1, 1, 20, 10},
};

bool isValidInput(int x, int y1, int y2) {
    return (x >= 0 && x < ROW && y1 >= 0 && y1 < COL && y2 >= 0 && y2 < COL);
}

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

int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
    if (!isValidInput(x, y1, y2))
        return INT_MIN;
    if (x == ROW-1 && y1 == 0 && y2 == COL-1)
        return (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];
    if (x == ROW-1)
        return INT_MIN;
    if (mTable[x][y1][y2] != -1)
        return mTable[x][y1][y2];
    
    int answer = INT_MIN;
    int temp = (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];
    
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1));
    
    return (mTable[x][y1][y2] = answer);
}

int findMaxCollection() {
    int mTable[ROW][COL][COL];
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            for(int k = 0; k < COL; k++)
                mTable[i][j][k] = -1;
    return findMaxVal(mTable, 0, 0, COL-1);
}

int main() {
    cout << "Maximum collection is " << findMaxCollection();
    return 0;
}

आउटपुट

Maximum collection is 73