আমাদের পূর্ণসংখ্যা উপাদান 지닌 একটি ২-D অ্যারে দেওয়া আছে যা ম্যাট্রিক্স তৈরি করে। কাজটি হল ম্যাট্রিক্স থেকে সাবম্যাট্রিক্স টেনে ন্যূনতম যোগফলের কাউন্ট গণনা করা।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
আউট - একটি দেওয়া ২D অ্যারেতে ন্যূনতম যোগফল সাবম্যাট্রিক্স: -9
ব্যাখ্যা - আমাদের ৪x৪ আকারের একটি ২-D অ্যারে দেওয়া আছে অর্থাৎ ৪টি রো এবং ৪টি কলাম। এখন, আমরা দেওয়া ম্যাট্রিক্স থেকে সাব-ম্যাট্রিক্স বের করব যাতে ন্যূনতম যোগফল -9 হয়।
ইন - int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
আউট - একটি দেওয়া ২D অ্যারেতে ন্যূনতম যোগফল সাবম্যাট্রিক্স: -3
ব্যাখ্যা - আমাদের ৩x৩ আকারের একটি ২-D অ্যারে দেওয়া আছে অর্থাৎ ৩টি রো এবং ৩টি কলাম। এখন, আমরা দেওয়া ম্যাট্রিক্স থেকে সাব-ম্যাট্রিক্স বের করব যাতে ন্যূনতম যোগফল -3 হয় যা দেওয়া ম্যাট্রিক্সের দ্বিতীয় রো দিয়ে অর্জিত হয় এবং সাব-ম্যাট্রিক্সের আকার হবে 1x3 অর্থাৎ ১টি রো এবং ৩টি কলাম।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি -
- একটি পূর্ণসংখ্যা ২-D অ্যারে ইনপুট নিন এবং ডেটা Minimum_Matrix(matrix) ফাংশনে পাস করুন आगे প্রসেসিং-এর জন্য।
- Minimum_Matrix(matrix) ফাংশনের ভিতরে:
- result = INT_MAX, arr[row], total, first এবং end নামে টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন।
- temp = ০ থেকে column পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে অ্যারে উপাদানগুলো ০ দিয়ে সেট করুন। temp_2 = temp থেকে column পর্যন্ত আরেকটি FOR লুপ শুরু করুন। লুপের ভিতরে, i = ০ থেকে row পর্যন্ত একটি লুপ শুরু করুন এবং arr[i] = arr[i] + matrix[i][temp_2] সেট করুন।
- total = Algo_Kad(arr, &first, &end, row) ফাংশন কল করে সেট করুন।
- চেক করুন IF total < result তবে result = total সেট করুন।
- চূড়ান্ত আউটপুট হিসেবে result প্রিন্ট করুন।
- int Algo_Kad(int* arr, int* first, int* end, int max_size) ফাংশনের ভিতরে:
- total = 0, result = INT_MAX, temp = 0 এবং *end = -1 নামে টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন।
- i = ০ থেকে max_size পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে 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 তবে result রিটার্ন করুন।
- result = arr[0], *first = 0 এবং *end = 0 সেট করুন।
- i = ১ থেকে max_size পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে চেক করুন IF arr[i] < result তবে result = arr[i], *first = i এবং *end = i সেট করুন।
- result রিটার্ন করুন।
উদাহরণ
#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
