C++-এ দুইজন মানুষ একবার মিলিত হয়ে ম্যাট্রিক্স-এ সর্বোচ্চ পয়েন্ট সংগ্রহ করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ম্যাট্রিক্স দেওয়া থাকলে যেটিতে প্রতিটি সেলে পয়েন্ট আছে। দুজন মানুষ দুটি কোণ থেকে শুরু করে একবার মিলিত হবে এবং সর্বোচ্চ পয়েন্ট সংগ্রহ করবে। প্রথম লোক: উপরের বাম থেকে নিচের ডান (ডান/নিচে)। দ্বিতীয় লোক: নিচের বাম থেকে উপরের ডান (ডান/উপরে)।

সমাধানের পদ্ধতি (4 DP Tables)

1. ৪টি DP টেবিল বানান:
   • P1S: উপরের বাম থেকে (i,j) পর্যন্ত সর্বোচ্চ পয়েন্ট।
   • P1E: (i,j) থেকে নিচের ডান পর্যন্ত সর্বোচ্চ পয়েন্ট।
   • P2S: নিচের বাম থেকে (i,j) পর্যন্ত সর্বোচ্চ পয়েন্ট।
   • P2E: (i,j) থেকে উপরের ডান পর্যন্ত সর্বোচ্চ পয়েন্ট।
2. মিটিং পয়েন্ট (i,j) এর জন্য (বর্ডার বাদে):
   • অপশন ১: P1 ডান→নিচ, P2 উপরে→ডান
   • অপশন ২: P1 নিচ→ডান, P2 ডান→উপরে
3. সর্বোচ্চ মান রিটার্ন করুন।

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 < N; i++) {
        for (int j = 2; j < M; j++) {
            int op1 = P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j];
            int op2 = P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1];
            ans = max(ans, max(op1, op2));
        }
    }
    return ans;
}

int main() {
    int A[][M] = {
        {100, 100, 100},
        {100, 1, 100},
        {100, 100, 100}
    };
    cout << "Max Points : " << findMaxPoints(A);
    return 0;
}

আউটপুট

Max Points : 800

ব্যাখ্যা

মিটিং পয়েন্ট (2,2) এ ১ বাদ দিয়ে সব ১০০ কালেক্ট করা হয়। ৮টি ১০০ = ৮০০।

জটিলতা

• সময়: O(N×M)
• স্থান: O(N×M)