समस्या कथन
एन पंक्तियों और एम कॉलम के बाइनरी मैट्रिक्स को देखते हुए। मैट्रिक्स पर अनुमत ऑपरेशन किसी भी इंडेक्स (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) चुनें।
एल्गोरिदम
विचार अंत बिंदु (एन -1, एम -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