আমরা C++।
সমস্যা বর্ণনা − এখানে, 2-D অ্যারে এবং k মুভের জন্য, আমাদের অ্যারের উপাদানগুলির দ্বারা তৈরি করা সংখ্যাটি খুঁজে বের করতে হবে। প্রতিটি পদক্ষেপে, আমরা একটি সারি বা কলাম নেব এবং সারি বা কলামের সমস্ত উপাদান ফ্লিপ করব। ম্যাট্রিক্সের একটি সারিতে K ফ্লিপ করার পরে আমাদের তৈরি হওয়া সংখ্যাটিকে সর্বাধিক করতে হবে তা মনে রাখার জন্য পছন্দটি করা হবে। এবং আমাদের সারিতে তৈরি সমস্ত সংখ্যার যোগফল ফেরত দিতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[][] = {
{1, 0, 0},
{0, 1, 1},
{1, 0, 1}
}
K = 2 আউটপুট
19
ব্যাখ্যা
আমাদের দুটি ফ্লিপ আছে,
প্রথম ফ্লিপ - আমরা 2য়-সারির উপাদানগুলি ফ্লিপ করব। এটি অ্যারে তৈরি করবে,
{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}} দ্বিতীয় ফ্লিপ - আমরা 2য় কলাম উপাদান উল্টানো হবে. এটি অ্যারে তৈরি করবে,
{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}} প্রতিটি সারিতে তৈরি চূড়ান্ত সংখ্যা হল 6, 6, 7।
Maximum sum = 19.
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের প্রথম কলাম 1 এর উপাদানটি প্রথমে তৈরি করতে হবে। ith কলামে 1 হিসাবে 2i তে অবদান রাখবে যা হবে সবচেয়ে বড় সম্ভাব্য সংখ্যা (যদি একটি সেট বিট বিবেচনা করা হয়)। সুতরাং, বাঁদিকের কলামে যোগফল সর্বোচ্চ করতে সর্বোচ্চ 1 এর (সেট বিট) থাকতে হবে। তারপর আমরা প্রতিটি সারির অন্যান্য উপাদানের জন্য যাব।
আমার সারি বা কলাম উল্টাতে হবে কিনা তা পরীক্ষা করতে। আমাদের কলামের অন্যান্য মান পরীক্ষা করতে হবে। অর্থাৎ সারির সমস্ত প্রথম উপাদান। যদি 0 এর সংখ্যা 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 "<<MaxSumAfterFlip(mat, K);
return 0;
} আউটপুট
The Maximum score after flipping the matrix atmost K times is 19
