ম্যাট্রিক্স গঠনকারী পূর্ণসংখ্যা উপাদানগুলির একটি 2-D অ্যারে দেওয়া হয়েছে। কাজটি হল এইভাবে গঠিত ম্যাট্রিক্স থেকে সাবম্যাট্রিক্স টেনে ন্যূনতম যোগফলের গণনা করা।
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
- মধ্যে int matrix[size][size] ={ {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
আউট - একটি প্রদত্ত 2D অ্যারেতে ন্যূনতম যোগফল সাবম্যাট্রিক্স হল:-9
ব্যাখ্যা - আমাদেরকে 4x4 আকারের একটি 2-D অ্যারে দেওয়া হয়েছে অর্থাৎ 4টি সারি এবং 4টি কলাম। এখন, আমরা প্রদত্ত ম্যাট্রিক্স থেকে সাব-ম্যাট্রিক্স বের করব যাতে ন্যূনতম সাব -9 হয়।
-এ int ম্যাট্রিক্স[সারি][কলাম] ={ {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
আউট - একটি প্রদত্ত 2D অ্যারেতে ন্যূনতম যোগফল সাবম্যাট্রিক্স হল:-3
ব্যাখ্যা - আমাদেরকে 3x3 আকারের একটি 2-D অ্যারে দেওয়া হয়েছে অর্থাৎ 3টি সারি এবং 3টি কলাম। এখন, আমরা প্রদত্ত ম্যাট্রিক্স থেকে সাব-ম্যাট্রিক্স খুঁজে বের করব যেমন ন্যূনতম সাব হল -3 যা একটি প্রদত্ত ম্যাট্রিক্সের দ্বিতীয় সারি দিয়ে অর্জন করা হয় এবং সাব-ম্যাট্রিক্সটি 1x3 আকারের হবে অর্থাৎ 1 সারি এবং 3টি কলাম।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -
-
একটি পূর্ণসংখ্যা 2-ডি অ্যারে ইনপুট করুন এবং আরও প্রক্রিয়াকরণের জন্য ন্যূনতম_ম্যাট্রিক্স(ম্যাট্রিক্স) ফাংশনে ডেটা পাস করুন৷
-
ন্যূনতম_ম্যাট্রিক্স(ম্যাট্রিক্স)
ফাংশনের ভিতরে-
অস্থায়ী ভেরিয়েবলগুলিকে int ফলাফল হিসাবে ঘোষণা করুন =INT_MAX, int arr[row], int total, int first এবং int end৷
-
স্টার্ট লুপ FOR int থেকে temp পর্যন্ত কলামের চেয়ে কম তাপমাত্রা পর্যন্ত। লুপের ভিতরে অ্যারে উপাদানগুলিকে 0 হিসাবে সেট করুন। int থেকে temp_2 পর্যন্ত temp_2 কলাম থেকে কম পর্যন্ত আরেকটি লুপ FOR শুরু করুন। লুপের ভিতরে, int i থেকে 0 থেকে i সারির কম না হওয়া পর্যন্ত আরেকটি লুপ শুরু করুন এবং arr[i] কে ar[i] + ম্যাট্রিক্স[i][temo_2] হিসাবে সেট করুন।
-
Algo_Kad(arr, &first, &end, row)
ফাংশনে কল হিসাবে মোট সেট করুন -
যদি মোট ফলাফলের চেয়ে কম হয় তাহলে ফলাফলটি মোট হিসাবে সেট করুন
-
চূড়ান্ত আউটপুট হিসাবে ফলাফল প্রিন্ট করুন৷
-
-
int Algo_Kad ফাংশনের ভিতরে(int* arr, int* first, int* end, int max_size)
-
অস্থায়ী ভেরিয়েবলগুলিকে int-টোটাল হিসাবে 0, int-এর ফলাফল INT_MAX-এ, int-টেম্প-এ 0 এবং *end =-1 হিসাবে ঘোষণা করুন
-
i থেকে 0 পর্যন্ত লুপ শুরু করুন যতক্ষণ না i max_size থেকে কম হয়। লুপের ভিতরে, মোট সেট করুন মোট + arr[i]।
-
0 এর থেকে বেশি হলে মোট 0 এবং temp হিসাবে i + 1 হিসাবে সেট করুন।
-
অন্যথায়, ফলাফলের চেয়ে মোট কম পরীক্ষা করুন তারপর ফলাফল সেট করুন মোট, *প্রথম থেকে টেম্প এবং *শেষ থেকে i
-
এখন, চেক করুন IF *end not equals to -1 তারপর ফলাফল দিন।
-
ফলাফল সেট করুন arr[0], *first to 0 এবং *end to 0
-
i থেকে 1 পর্যন্ত FOR লুপ শুরু করুন যতক্ষণ না i max_size থেকে কম হয়। লুপের ভিতরে, ফলাফলের চেয়ে IF arr[i] কম চেক করুন তারপর arr[i] হিসাবে ফলাফল সেট করুন, *প্রথমে i হিসাবে এবং *শেষ i হিসাবে
-
ফলাফল ফেরত।
-
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define row 4
#define column 4
int Algo_Kad(int* arr, int* first, int* end, int max_size)
{
int total = 0;
int result = INT_MAX;
int temp = 0;
*end = -1;
for(int i = 0; i < max_size; ++i)
{
total = total + arr[i];
if(total > 0)
{
total = 0;
temp = i + 1;
}
else if(total < result)
{
result = total;
*first = temp;
*end = i;
}
}
if(*end != -1)
{
return result;
}
result = arr[0];
*first = 0;
*end = 0;
for(int i = 1; i < max_size; i++)
{
if(arr[i] < result)
{
result = arr[i];
*first = i;
*end = i;
}
}
return result;
}
void Minimum_Matrix(int matrix[][column])
{
int result = INT_MAX;
int arr[row];
int total;
int first;
int end;
for(int temp = 0; temp < column; ++temp)
{
memset(arr, 0, sizeof(arr));
for(int temp_2 = temp; temp_2 < column; ++temp_2)
{
for(int i = 0; i < row; ++i)
{
arr[i] = arr[i] + matrix[i][temp_2];
}
total = Algo_Kad(arr, &first, &end, row);
if(total < result)
{
result = total;
}
}
}
cout<<"Minimum sum submatrix in a given 2D array is: "<<result;
}
int main()
{
int matrix[row][column] = {{2, 3, -1, 5},
{-2, 9, -1, 6},
{ 5, 6, 9, -9},
{ -6, 1, 1, 1} };
Minimum_Matrix(matrix);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Minimum sum submatrix in a given 2D array is: -9
