দেওয়া যোগফলযুক্ত সাব-ম্যাট্রিক্স খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি 2D ম্যাট্রিক্স দেওয়া আছে আকার N*N এবং দুটি ভেরিয়েবল sum এবং size। আমাদের কাজ হল দেওয়া যোগফলযুক্ত একটি সাব-ম্যাট্রিক্স খুঁজে বের করা।

আমাদের size*size আকারের একটি সাব-ম্যাট্রিক্স খুঁজে বের করতে হবে যার উপাদানগুলোর যোগফল sum-এর সমান।

উদাহরণ

সমস্যাটি বুঝতে একটি উদাহরণ নিই:

ইনপুট : mat[][] = {
    {1, 5, 7, 9}
    {2, 4, 6, 8}
    {1, 2, 5, 6}
    {3, 6, 9, 3}
} sum = 22 Size = 2
আউটপুট : YES

ব্যাখ্যা:

আকার k-এর সাবম্যাট্রিক্স যার যোগফল 22: {5, 7} {4, 6}

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হল সব সম্ভাব্য size*size আকারের সাবঅ্যারে তৈরি করা, তাদের যোগফল বের করা এবং তারপর দেওয়া যোগফলের সাথে তুলনা করা। যদি দুটি সমান হয়, true রিটার্ন করুন।

একটি অন্য পদ্ধতি হল ডাইনামিক প্রোগ্রামিং অ্যালগরিদম ব্যবহার করা। এই পদ্ধতিতে, আমরা একটি DP অ্যারে তৈরি করব যা বর্তমান ইনডেক্স পর্যন্ত যোগফল সংরক্ষণ করবে। অর্থাৎ DP[i][j] সারি ০ থেকে i এবং কলাম ০ থেকে j পর্যন্ত সব উপাদানের যোগফল সংরক্ষণ করবে।

এই DP অ্যারে ব্যবহার করে, আমরা যেকোনো দুটি শুরুর ইনডেক্স এবং শেষ ইনডেক্সের মধ্যে যোগফল নিচের ফর্মুলা দিয়ে বের করব:

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[i_s][i_e]\:-\:DP[i_e][i_s]}$$

অ্যালগরিদম

স্টেপ ১ − আকার (n+1)*(n+1) এর একটি DP ম্যাট্রিক্স তৈরি করুন।

স্টেপ ২ − ম্যাট্রিক্সের প্রতিটি উপাদানের জন্য, বর্তমান ইনডেক্স পর্যন্ত যোগফল বের করুন।

স্টেপ ৩ − 0 থেকে n পর্যন্ত সব ইনডেক্সের জন্য, size*size আকারের সাব-ম্যাট্রিক্সের যোগফল ফর্মুলা ব্যবহার করে বের করুন এবং currSum-এ সংরক্ষণ করুন।

স্টেপ ৪ − যদি currSum == sum হয়, true রিটার্ন করুন।

স্টেপ ৫ − false রিটার্ন করুন।

উদাহরণ প্রোগ্রাম

আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:

#include <iostream>
using namespace std;

#define N 4

bool findSubMatWithSum(int size, int sum, int mat[N][N]) {
    int DP[N + 1][N + 1];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];

    int currSum = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
            if (currSum == sum)
                return true;
        }
    return false;
}

int main() {
    int mat[N][N] = {
        { 1, 5, 7, 9 },
        { 2, 4, 6, 8 },
        { 1, 2, 5, 6 },
        { 3, 6, 9, 3 }
    };
    int size = 2;
    int sum = 22;
    if (findSubMatWithSum(size, sum, mat))
        cout << "Sub-Matrix of given size having the given sum is possible!";
    else
        cout << "Sub-Matrix of given size having the given sum is not possible!";
}

আউটপুট

Sub-Matrix of given size having the given sum is possible!