C++ में एक बार मिलने की अनुमति के साथ दो व्यक्तियों द्वारा अधिकतम अंक एकत्र करना

अंकों वाली मैट्रिक्स दी गई है। दो व्यक्ति दो कोनों से शुरू होकर एक बार मिलते हैं और अधिकतम अंक एकत्र करते हैं। पथ इस तरह चुनें कि कुल अंक अधिकतम हों।

चार DP टेबल: प्रत्येक व्यक्ति के लिए शुरुआत से मिलन बिंदु तक और मिलन बिंदु से अंत तक। सभी संभावित मिलन बिंदुओं के लिए अधिकतम जोड़ देखें।

उदाहरण 3x3 मैट्रिक्स के लिए अधिकतम अंक 800।

C++ कार्यान्वयन

#include <bits/stdc++.h>
#define M 3
#define N 3
using namespace std;

int findMaxPoints(int A[][M]) {
    int P1S[M+1][N+1], P1E[M+1][N+1];
    memset(P1S, 0, sizeof(P1S));
    memset(P1E, 0, sizeof(P1E));
    int P2S[M+1][N+1], P2E[M+1][N+1];
    memset(P2S, 0, sizeof(P2S));
    memset(P2E, 0, sizeof(P2E));
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
        for (int j=M; j>=1; j--)
            P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
        for (int j=1; j<=M; j++)
            P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
    for (int i=1; i<=N; i++)
        for (int j=M; j>=1; j--)
            P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
    int ans = 0;
    for (int i=2; i
आउटपुट
Max Points : 800