cpp 解法, 执行用时: 4 ms, 内存消耗: 8.7 MB, 提交时间: 2023-10-21 20:24:14

const int N = 1e5 + 7;
class Solution {
public:
    int dp[N];
    int st[N];
    int removeOnes(vector<vector<int>>& grid) {
        int n,m;
        n = grid.size() , m = grid[0].size();
        int S = 0;
        // (i,j) -> i * m + j
        // S 表示全部 1 的状态
        for(int i = 0;i < n;i ++) {
            for(int j = 0;j < m;j ++) {
                if(grid[i][j]) S ^= (1 << (i * m + j));
            }
        }
        if(!S) return 0;
        if(n == 1 || m == 1) return 1;// 小剪枝
        dp[0] = 0;
        int all = n * m;// 全部位数 
        // st[] 存从大到小的所有合法状态 (子集枚举)
        int top = 0;
        for(int sub = S;sub;sub = (sub - 1) & S) {
            st[top ++] = sub;
        }
        // 从小到大枚举全部状态
        for(int o = top - 1;o >= 0;o --) {
            int i = st[o];// i 表示当前要求的状态
            dp[i] = n;
            for(int j = 0;j < all;j ++) {
                // 枚举可以移除的点的位置
                if(i >> j & 1) {
                    int t = i;
                    // (j / m , j % m) 为点 -> (x,y)
                    int x = j / m , y = j % m;
                    // 处理 行 x
                    for(int k = 0;k < m;k ++) {
                        if(t >> (x * m + k) & 1) t ^= (1 << (x * m + k));
                    }
                    // 处理 列 y
                    for(int k = 0;k < n;k ++) {
                        if(t >> (k * m + y) & 1) t ^= (1 << (k * m + y));
                    }
                    // 移除 (x,y) 需要 1 次 剩下的需要 dp[t] 次
                    dp[i] = min(dp[i],dp[t] + 1);
                }
            }
        }
        return dp[S];
    }
};

python3 解法, 执行用时: 32 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-21 20:23:31

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        stack = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    stack.append([i, j])

        def dfs(stack):
            if not stack:
                return 0
            ans = float('inf')
            for rem in stack:
                nex = []
                for node in stack:
                    if node[0] != rem[0] and node[1] != rem[1]:
                        nex.append(node)
                ans = min(ans, dfs(nex) + 1)
            return ans

        return dfs(stack)

python3 解法, 执行用时: 52 ms, 内存消耗: 16 MB, 提交时间: 2023-10-21 20:23:19

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> int:
        queue = collections.deque()
        n,m = len(grid),len(grid[0])
        queue.append([grid,0])
        while queue:
            cur,step = queue.popleft()
            flag = 1
            
            for i in range(n):
                for j in range(m):
                    if cur[i][j]:
                        flag = 0
                        break
                if not flag:
                    break
            if flag:
                return step
            
            for i in range(n):
                for j in range(m):
                    if cur[i][j]:
                        temp = copy.deepcopy(cur)
                        for k in range(m):
                            if cur[i][k]:
                                temp[i][k] = 0
                        for k in range(n):
                            if cur[k][j]:
                                temp[k][j] = 0
                        queue.append([temp,step + 1])

golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-10-21 20:23:01

func removeOnes(grid [][]int) int {
	var points [][]int
	m, n := len(grid), len(grid[0])
	mask := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				points = append(points, []int{i, j})
				mask += 1 << (i*n + j)
			}

		}
	}
	ans := len(points)
	total := 1 << len(points)
    all:= (1<<(m*n))-1
	for i := 1; i < total; i++ {
		temp := mask
		count := bitLen(i)
		if count > ans {
			continue
		}
		for j := 0; j < len(points); j++ {
			if (1<<j)&i > 0 {
				for k := 0; k < m; k++ {
					temp &= all - (1 << (k*n + points[j][1]))
				}
				for k := 0; k < n; k++ {
					temp &= all - (1 << (points[j][0]*n + k))
				}
			}
		}
		if temp == 0 {
			ans = count
		}
	}
	return ans
}

func bitLen(i int)int{
    ans:=0
    for i >0{
        ans++
        i &= i-1
    }
    return ans
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.8 MB, 提交时间: 2023-10-21 20:22:42

class Solution {
    private int ans;
    public int removeOnes(int[][] grid) {
        // 为了节省空间，用1个数字表示坐标点
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(grid[i][j] == 1){
                    list.add(i * 16 + j);
                }
            }
        }
        // 递归处理所有可能情况，返回最小操作次数
        ans = Integer.MAX_VALUE;
        dfs(list, 0);
        return ans;
    }
    // 递归函数含义：剩余'1'的坐标列表为list，已经执行了step步，遍历当前删除各个'1'的情况
    public void dfs(List<Integer> list, int step){
        // 数组中不在有1时，取最小操作次数返回
        if(list.size() == 0){
            ans = Math.min(ans, step);
            return;
        }
        // 遍历list中所有的1，针对每个1都删掉行列的1之后再继续递归
        int size = list.size();
        for(int k = 0; k < size; k ++){
            int i = list.get(k) / 16;
            int j = list.get(k) % 16;
            List<Integer> newList = new ArrayList<>();
            for(int num: list){
                if(num / 16 != i && num % 16 != j){
                    newList.add(num);
                }
            }
            dfs(newList, step + 1);
        }
    }
}