এই সমস্যায় একটি ২D অ্যারে arr[] (০ এবং ১) এবং পূর্ণসংখ্যা K দেওয়া আছে। আমাদের C++-এ বাইনারি ম্যাট্রিক্সสูচক K বার ফ্লিপ করে সর্বোচ্চ স্কোর বের করার প্রোগ্রাম লিখতে হবে।
সমস্যার বিবরণ - ২D অ্যারে এবং K মুভ দেওয়া আছে। প্রতিটি মুভে একটি সারি বা কলামের সব উপাদান ফ্লিপ করতে হবে (০→১, ১→০)। লক্ষ্য হল K মুভ পর প্রতিটি সারির বাইনারি সংখ্যা থেকে তৈরি মোট সংখ্যার যোগফল সর্বোচ্চ করা।
উদাহরণ:
ইনপুট
arr[][] = {{1, 0, 0}, {0, 1, 1}, {1, 0, 1}}, K = 2আউটপুট
19
ব্যাখ্যা
প্রথম ফ্লিপ: ২য় সারি → {{1,0,0},{1,0,0},{1,0,1}}। দ্বিতীয় ফ্লিপ: ২য় কলাম → {{1,1,0},{1,1,0},{1,1,1}}। প্রতিটি সারির সংখ্যা: ৬, ৬, ৭। মোট = ১৯।
সমাধানের পদ্ধতি
প্রথম কলামের সব উপাদান ১ করা যাক (সর্বোচ্চ ওজন)। তারপর প্রতিটি কলামে ০ বেশি হলে সেটি ফ্লিপ করুন। ম্যাপ ডেটা স্ট্রাকচার ব্যবহার করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
map<int, int> flipValues;
int updateVal, MaxSum = 0;
for (int i = 0; i < row; ++i) {
if (mat[i][0] == 0) {
updateVal = 0;
for (int j = 1; j < col; ++j)
updateVal = updateVal + mat[i][j] * pow(2, col - j - 1);
flipValues[updateVal] = i;
}
}
map<int, int>::iterator it = flipValues.begin();
while (K > 0 && it != flipValues.end()) {
int updateIndex = it->second;
for (int j = 0; j < col; ++j)
mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
it++;
K--;
}
MaxSum = 0;
int zeros, ones = 0;
for (int j = 0; j < col; ++j) {
zeros = ones = 0;
for (int i = 0; i < row; ++i) {
mat[i][j] == 0 ? zeros++ : ones++;
}
if (K > 0 && zeros > ones) {
MaxSum += zeros * pow(2, (col - j - 1));
K--;
}
else
MaxSum += ones * pow(2, (col - j - 1));
}
return MaxSum;
}
int main() {
int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
int K = 2;
cout<<"The Maximum score after flipping the matrix atmost K times is "<আউটপুট
The Maximum score after flipping the matrix atmost K times is 19
