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.

c++

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);
    }
};