समस्या विवरण
N पंक्तियों और M कॉलम का एक बाइनरी मैट्रिक्स दिया गया है। मैट्रिक्स पर अनुमत ऑपरेशन किसी भी इंडेक्स (x, y) को चुनना और उस आयत के सभी एलिमेंट्स को टॉगल करना है जिसका टॉप-लेफ्ट (0, 0) और बॉटम-राइट (x-1, y-1) है। एलिमेंट को टॉगल करने का अर्थ है 1 को 0 और 0 को 1 में बदलना। कार्य मैट्रिक्स के सभी एलिमेंट्स को सेट करने के लिए आवश्यक न्यूनतम ऑपरेशन्स ढूंढना है यानी सभी एलिमेंट्स को 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}
तो उत्तर 1 है एक चाल में, (3, 3) चुनकर पूरे मैट्रिक्स को केवल 1s से युक्त बनाया जा सकता है।
एल्गोरिदम
विचार अंतिम बिंदु (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
