[LeetCode] Remove All Ones With Row and Column Flips II

2174. Remove All Ones With Row and Column Flips II

You are given a 0-indexed m x n binary matrix grid.

In one operation, you can choose any i and j that meet the following conditions:

  • 0 <= i < m
  • 0 <= j < n
  • grid[i][j] == 1

and change the values of all cells in row i and column j to zero.

Return the minimum number of operations needed to remove all 1’s from grid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
int n, m;
int dp[1<<17];
int helper(int st) {
if(!st) return 0;
if(dp[st]!= -1) return dp[st];
dp[st] = INT_MAX;
for(int i = 0; i < n; i++) {
for(int j =0; j < m; j++) {
if(st & (1<<(i*m + j))) {
int nt = st;
for(int k = 0; k < n; k++) nt &= ~(1<<(k*m + j));
for(int k = 0; k < m; k++) nt &= ~(1<<(i*m + k));
dp[st] = min(dp[st], 1 + helper(nt));
}
}
}
return dp[st];
}
public:
int removeOnes(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
memset(dp,-1,sizeof(dp));
int state = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(grid[i][j])
state |= 1<<(i*m+j);
return helper(state);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/28/PS/LeetCode/remove-all-ones-with-row-and-column-flips-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.