이진 행렬이 하나 있다고 가정합니다. 행을 뒤집은 다음 열을 뒤집을 때 얻을 수 있는 최대 1 수를 찾아야 합니다.
입력이 다음과 같으면
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
그러면 출력은 8이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=행렬의 행 크기
-
m :=행렬의 열 크기
-
ret :=0
-
크기가 n인 배열 행 정의
-
크기가 n인 배열 열 정의
-
총계 :=0
-
initialize i :=0의 경우, i
-
j 초기화의 경우:=0, j
-
행[i] :=행[i] + 행렬[i, j]
-
col[j] :=col[j] + 행렬[i, j]
-
총계 :=총계 + 행렬[i, j]
-
-
-
initialize i :=0의 경우, i
-
j 초기화의 경우:=0, j
-
cand :=총계 - 행[i] - 열[j] + ((m - 행[i]) + (n - 열[j]))
-
행렬[i, j]가 0이 아니면 -
-
캔디 :=캔디 + 2
-
-
그렇지 않으면
-
캔드 :=캔디 - 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