ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। একটি সারি ফ্লিপ করলে এবং তারপর একটি কলাম ফ্লিপ করলে আমাদের সর্বাধিক 1 সেকেন্ড পেতে হবে৷
সুতরাং, যদি ইনপুটটি এরকম হয়
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
তাহলে আউটপুট হবে 8
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=ম্যাট্রিক্সে সারির আকার
-
m :=ম্যাট্রিক্সে কলামের আকার
-
ret :=0
-
n
আকারের একটি অ্যারে সারি সংজ্ঞায়িত করুন -
n
আকারের একটি অ্যারে কল সংজ্ঞায়িত করুন -
মোট :=0
-
আরম্ভ করার জন্য i :=0, যখন i
-
j শুরু করার জন্য :=0, যখন j
-
সারি[i] :=সারি[i] + ম্যাট্রিক্স[i, j]
-
col[j] :=col[j] + ম্যাট্রিক্স[i, j]
-
মোট :=মোট + ম্যাট্রিক্স[i, j]
-
-
-
আরম্ভ করার জন্য i :=0, যখন i
-
j শুরু করার জন্য :=0, যখন j
-
cand :=মোট - সারি[i] - col[j] + ((m - row[i]) + (n - col[j]))
-
যদি ম্যাট্রিক্স[i, j] অ-শূন্য হয়, তাহলে −
-
cand :=cand + 2
-
-
অন্যথায়
-
cand :=cand - 2
-
-
ret :=সর্বোচ্চ ret এবং cand
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
