मान लीजिए कि हमारे पास दो आयामी मैट्रिक्स ए है जहां प्रत्येक मान 0 या 1 है। यहां एक चाल में किसी भी पंक्ति या कॉलम को चुनना और उस पंक्ति या कॉलम में प्रत्येक मान को टॉगल करना शामिल है:सभी 0s से 1s, और सभी 1s से 0s को बदलना। अब कितनी भी चालें चलने के बाद, इस मैट्रिक्स की प्रत्येक पंक्ति को एक द्विआधारी संख्या के रूप में व्याख्यायित किया जाता है, और मैट्रिक्स का स्कोर इन संख्याओं का योग होता है। तो हमारा काम उच्चतम संभव स्कोर खोजना है। अगर इनपुट इस तरह है -
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
आउटपुट 39 होगा क्योंकि टॉगल करने के बाद मैट्रिक्स होगा -
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
तो संख्याएँ हैं 15 + 9 + 15 =39
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=पंक्ति गणना और m :=स्तंभ गणना
-
रिट :=n x (2^(m - 1))
-
j के लिए 1 से m - 1 की सीमा में
-
सीएनटी:=0
-
मेरे लिए 0 से n - 1 की सीमा में
-
सीएनटी:=सीएनटी + ए [i, जे] =ए [i, 0]
-
-
अस्थायी:=2^(m - j - 1) * अधिकतम cnt और n - cnt
-
रिट :=रिट + टेम्प
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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