मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। हमें अधिकतम 1s की संख्या ज्ञात करनी है जो हम प्राप्त कर सकते हैं यदि हम एक पंक्ति और फिर एक स्तंभ को फ्लिप करते हैं।
उदाहरण के लिए, यदि इनपुट है:
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
8 होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
n := मैट्रिक्स में पंक्तियों का आकारm := मैट्रिक्स में स्तंभों का आकारret := 0- आकार
nकी एक सरणीrowपरिभाषित करें - आकार
mकी एक सरणीcolपरिभाषित करें total := 0i := 0सेn-1तक लूप चलाएं:j := 0सेm-1तक लूप चलाएं:row[i] := row[i] + matrix[i][j]col[j] := col[j] + matrix[i][j]total := total + matrix[i][j]
i := 0सेn-1तक लूप चलाएं:j := 0सेm-1तक लूप चलाएं:cand := total - row[i] - col[j] + ((m - row[i]) + (n - col[j]))- यदि
matrix[i][j]शून्येतर है:cand := cand + 2
- अन्यथा:
cand := cand - 2
ret := ret और cand का अधिकतम
retलौटाएं।
C++ कार्यान्वयन
#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;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{1, 0, 1}, {0, 1, 0}, {1, 0, 0}};
cout << (ob.solve(v));
return 0;
}
इनपुट
{{1, 0, 1}, {0, 1, 0}, {1, 0, 0}}
आउटपुट
8