সমস্যা বিবৃতি
N সারি এবং M কলামের একটি বাইনারি ম্যাট্রিক্স দেওয়া হয়েছে। ম্যাট্রিক্সে অনুমোদিত অপারেশন হল যেকোনো সূচক (x, y) বেছে নেওয়া এবং উপরের-বাম দিকে (0, 0) এবং নীচে-ডানে (x-1, y-1) হিসাবে আয়তক্ষেত্রের মধ্যে সমস্ত উপাদান টগল করা। উপাদানটিকে টগল করার অর্থ হল 1 থেকে 0 এবং 0 থেকে 1 পরিবর্তন করা। কাজটি হল ম্যাট্রিক্সের সমস্ত উপাদান সেট করার জন্য প্রয়োজনীয় ন্যূনতম ক্রিয়াকলাপগুলি খুঁজে বের করা অর্থাৎ সমস্ত উপাদানকে 1 হিসাবে তৈরি করা।
উদাহরণ
If input matrix is {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}
Then answer is 1 শুধুমাত্র 1s সমন্বিত সমগ্র ম্যাট্রিক্স তৈরি করতে এক চালে (3, 3) বেছে নিন।
অ্যালগরিদম
ধারণাটি শেষ বিন্দু থেকে শুরু করা (N – 1, M – 1) এবং ম্যাট্রিক্সটিকে বিপরীত ক্রমে অতিক্রম করা। যখনই আমরা এমন একটি ঘরের মুখোমুখি হই যার মান 0, এটিকে ফ্লিপ করুন
উদাহরণ
#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
