C++-এ ম্যাট্রিক্স-এ উপরের বাম থেকে নিচের ডান যেতে এবং ফিরে আসতে সর্বোচ্চ পয়েন্ট সংগ্রহ করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ম্যাট্রিক্স দেওয়া থাকলে যেটিতে '#' = ব্লকড, '*' = পয়েন্ট, '.' = পথ। উপরের বাম কোণ থেকে নিচের ডান কোণে যান (ডান/নিচে মুভ) এবং ফিরে আসুন (বাম/উপরে মুভ) যাতে সর্বোচ্চ '*' সংগ্রহ হয়। দুজন মানুষ একসাথে যাচ্ছে এবং একবার মিলিত হচ্ছে এমন সমান দৃশ্য।

সমাধানের পদ্ধতি (DP with 3D State)

1. দুই পথ একসাথে সিমুলেট করুন: (row1, col1) এবং (row2, col2)।
2. স্টেট: dp[row1][col1][row2] (col2 = row1+col1-row2)।
3. ট্রানজিশন: ৪টি কম্বিনেশন (RR, RD, DR, DD)।
4. বেস কেস: গন্তব্যে পৌঁছলে ০। ব্লকড হলে -inf।
5. পয়েন্ট কালকুলেশন: দুটি পথ একই সেলে হলে একবার কাউন্ট।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;

int cost(char grid[][M], int row1, int col1, int row2, int col2) {
    if (row1 == row2 && col1 == col2) {
        if (grid[row1][col1] == '*') return 1;
        return 0;
    }
    int ans = 0;
    if (grid[row1][col1] == '*') ans++;
    if (grid[row2][col2] == '*') ans++;
    return ans;
}

int solve(int n, int m, char grid[][M], int dp[MAX][MAX][MAX], int row1, int col1, int row2) {
    int col2 = (row1 + col1) - (row2);
    if (row1 == n-1 && col1 == m-1 && row2 == n-1 && col2 == m-1) return 0;
    if (row1 >= n || col1 >= m || row2 >= n || col2 >= m) return -inf;
    if (dp[row1][col1][row2] != -1) return dp[row1][col1][row2];
    
    int ch1 = -inf, ch2 = -inf, ch3 = -inf, ch4 = -inf;
    if (grid[row1][col1+1] != '#' && grid[row2+1][col2] != '#')
        ch1 = cost(grid, row1, col1+1, row2+1, col2) + solve(n, m, grid, dp, row1, col1+1, row2+1);
    if (grid[row1][col1+1] != '#' && grid[row2][col2+1] != '#')
        ch2 = cost(grid, row1, col1+1, row2, col2+1) + solve(n, m, grid, dp, row1, col1+1, row2);
    if (grid[row1+1][col1] != '#' && grid[row2][col2+1] != '#')
        ch3 = cost(grid, row1+1, col1, row2, col2+1) + solve(n, m, grid, dp, row1+1, col1, row2);
    if (grid[row1+1][col1] != '#' && grid[row2+1][col2] != '#')
        ch4 = cost(grid, row1+1, col1, row2+1, col2) + solve(n, m, grid, dp, row1+1, col1, row2+1);
    
    return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}

int wrapper(int n, int m, char grid[N][M]) {
    int ans = 0;
    int dp[MAX][MAX][MAX];
    memset(dp, -1, sizeof dp);
    if (grid[n-1][m-1] == '#' || grid[0][0] == '#') ans = -inf;
    if (grid[0][0] == '*') ans++;
    grid[0][0] = '.';
    if (grid[n-1][m-1] == '*') ans++;
    grid[n-1][m-1] = '.';
    ans += solve(n, m, grid, dp, 0, 0, 0);
    return max(ans, 0);
}

int main() {
    int n = 5, m = 5;
    char grid[N][M] = {
        {'.', '*', '.', '*', '.'},
        {'*', '#', '#', '#', '.'},
        {'*', '.', '*', '.', '*'},
        {'.', '#', '#', '#', '*'},
        {'.', '*', '.', '*', '.'}
    };
    cout << wrapper(n, m, grid) << endl;
    return 0;
}

আউটপুট

8

জটিলতা

• সময়: O(N² × M) — ৩D DP স্টেট
• স্থান: O(N² × M)