मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। यदि हम एक पंक्ति को फ्लिप करते हैं और फिर एक कॉलम को फ्लिप करते हैं, तो हमें अधिकतम 1s प्राप्त करना होगा।
तो, अगर इनपुट पसंद है
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
तो आउटपुट 8
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=मैट्रिक्स में पंक्तियों का आकार
-
m :=मैट्रिक्स में कॉलम का आकार
-
रिट:=0
-
आकार n की एक सरणी पंक्ति को परिभाषित करें
-
आकार n के एक सरणी कोल को परिभाषित करें
-
कुल:=0
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
पंक्ति [i]:=पंक्ति [i] + मैट्रिक्स [i, j]
-
कर्नल [जे]:=कर्नल [जे] + मैट्रिक्स [i, जे]
-
कुल:=कुल + मैट्रिक्स [i, j]
-
-
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
कैंड:=कुल - पंक्ति [i] - col[j] + ((m - row[i]) + (n - col[j]))
-
अगर मैट्रिक्स [i, j] गैर-शून्य है, तो -
-
कैंड :=कैंड + 2
-
-
अन्यथा
-
कैंडी:=कैंडी - 2
-
-
रिट :=अधिकतम रिट और कैंडिडेट
-
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
int ret = 0;
vector<int> row(n);
vector<int> col(m);
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
row[i] += matrix[i][j];
col[j] += matrix[i][j];
total += matrix[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cand = total - row[i] - col[j] + (m - row[i]) + (n -
col[j]);
if (matrix[i][j]) {
cand += 2;
}else {
cand -= 2;
}
ret = max(ret, cand);
}
}
return ret;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,1,0},{1,0,0}};
cout << (ob.solve(v));
} इनपुट
{{1,0,1},{0,1,0},{1,0,0}} आउटपुट
8