সমস্যা বিবরণ
N রো এবং M কলামের একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। ম্যাট্রিক্সে অনুমোদিত অপারেশন হলো যেকোনো ইনডেক্স (x, y) বেছে নেওয়া এবং (0, 0) থেকে (x-1, y-1) পর্যন্ত আয়তক্ষেত্রের সব এলিমেন্ট টগল করা। টগল মানে ১ কে ০ এবং ০ কে ১ করা। টাস্ক হলো মিনিমাম অপারেশন বের করা যাতে ম্যাট্রিক্সের সব এলিমেন্ট ১ হয়।
উদাহরণ
ইনপুট ম্যাট্রিক্স:
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{1, 1, 1, 1, 1}
{1, 1, 1, 1, 1}
তब উত্তর ১
একটি মুভে (3, 3) বেছে নিলে পুরো ম্যাট্রিক্স শুধু ১ দিয়ে গঠিত হবে।
অ্যালগরিদম
আইডিয়া হলো এন্ড পয়েন্ট (N-1, M-1) থেকে শুরু করে ম্যাট্রিক্স রিভার্স অর্ডারে ট্রাভার্স করা। যেকোনো সেলে ০ পাওয়া গেলে সেটি ফ্লিপ করুন।
উদাহরণ
#include <iostream>
#define ROWS 5
#define COLS 5
using namespace std;
int getMinOperations(bool arr[ROWS][COLS]) {
int ans = 0;
for (int i = ROWS - 1; i >= 0; i--) {
for (int j = COLS - 1; j >= 0; j--) {
if (arr[i][j] == 0) {
ans++;
for (int k = 0; k <= i; k++) {
for (int h = 0; h <= j; h++) {
if (arr[k][h] == 1)
arr[k][h] = 0;
else
arr[k][h] = 1;
}
}
}
}
}
return ans;
}
int main() {
bool mat[ROWS][COLS] = {
0, 0, 1, 1, 1,
0, 0, 0, 1, 1,
0, 0, 0, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1
};
cout << "Minimum required operations = " << getMinOperations(mat) << endl;
return 0;
}
আউটপুট
যখন আপনি উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে:
Minimum required operations = 3
