মান লেযিয়ে একটি ২D ম্যাট্রিক্স A দেওয়া আছে যেখানে প্রতিটি মান ০ বা ১। একটি মুভ হল যেকোনো সারি বা কলাম বেছে নিয়ে সেটির সব মান টগল করা: ০ কে ১, ১ কে ০। যেকোনো সংখ্যক মুভ করার পর, প্রতিটি সারি একটি বাইনারি নম্বর হিসেবে ইন্টারপ্রেট করা হবে, এবং ম্যাট্রিক্সের স্কোর হবে এই নম্বরগুলোর যোগফল। সর্বোচ্চ সম্ভাব্য স্কোর খুঁজে বের করতে হবে। ইনপুট -
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
আউটপুট ৩৯। টগল করার পর ম্যাট্রিক্স -
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
নম্বরগুলো ১৫ + ৯ + ১৫ = ৩৯।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := সারি সংখ্যা, m := কলাম সংখ্যা
ret := n * (2^(m-1))
j = 1 থেকে m-1 পর্যন্ত লুপ চালান
cnt := 0
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
cnt := cnt + (A[i][j] == A[i][0])
temp := 2^(m-j-1) * max(cnt, n-cnt)
ret := ret + temp
ret রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int matrixScore(vector<vector<int>>& A) { int n = A.size(); int m = A[0].size(); int ret = (1 << (m - 1)) * n; for(int j = 1; j < m; j++){ int cnt = 0; for(int i = 0; i < n; i++){ cnt += (A[i][j] == A[i][0]); } int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt)); ret += temp; } return ret; } }; main(){ vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}}; Solution ob; cout << (ob.matrixScore(v)); }ইনপুট
[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
আউটপুট
39
