1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge.

Return the  minimum number of steps  required to convert mat to a zero matrix or -1 if you cannot.

A binary matrix is a matrix with all cells equal to 0 or 1 only.

A zero matrix is a matrix with all cells equal to 0.

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We do not need to change it.

Example 3:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix cannot be a zero matrix.

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 3
  • mat[i][j] is either 0 or 1.

这道题给了一个 m by n 的二维数组,只包含数字0或者1,现在说是可以任意选一个位置翻转数字,同时该位置周围的四个位置(若存在的话)也需要被反转,问最少需要翻转多少次可以将整个数组变为只含有0的数组。通过分析题目给的例子不难理解题意,首先来想,如果不考虑代码实现,给你一个任意数组,该怎么翻转成全0的数组,实际上是不好做的,因为很有可能翻转成之前已经存在的状态,并一直重复下去,很难翻成全0数组。这就像是一个迷宫,起始状态就是给定的数组,结束状态就是全0的数组,那么遍历迷宫的最少步数就是需要用广度优先遍历 Breadth-first Search 来做。每一个位置的状态就是当前数组的值,直接保留二维数组的话运算起来不是很高效,因为需要查重运算。这里用一个 trick 把二维数组编码成一个整型数,因为题目限定了m和n的大小不超过3,则数组中最多只有9个数字,可以把每个数字放到整型数的一个 bit 上,正好数组中只有0和1,可以完美的表示成二进制数,这样每个数组的情况就可以用一个二进制数表示了,理解了这个之后代码也就不难写了。

首先把起始状态编码成一个整型数,做法是把二维坐标变成一维坐标,通过 i*n + j 来实现,然后再将 mat[i][j] 左移 i*n + j 位, 上 start 即可。然后就是 BFS 的传统写法了,用一个队列 queue,把 start 放进去,再用一个 HashSet 来查重,把 start 放进去。进行 while 循环,里面再用一个 for 循环,保证了是一层一层向外扩散的。先取出队首元素 cur,若 cur 为0,表示当前的数组全为0了,把当前步数 res 返回即可。否则就要尝试将每个数字都翻转一下,看是否会生成新的状态,遍历二维数组的每个位置,复制 cur 到 next,然后要翻转当前位置和相邻的四个位置,这样 dirs 数组中就有5个 offset 值,若新位置没有越界,则将 next 对应的 bit 位翻转,然后看这个新的整型数是否在 HashSet 中,不在的话加入 HashSet,并且排入队列继续遍历。每遍历完一层,步数 res 自增1,若 while 退出,返回 -1 即可,参见代码如下:

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int res = 0, m = mat.size(), n = mat[0].size(), start = 0;
        vector<vector<int>> dirs{{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                start |= mat[i][j] << (i * n + j);
            }
        }
        queue<int> q{{start}};
        unordered_set<int> visited{{start}};
        while (!q.empty()) {
            for (int t = q.size(); t > 0; --t) {
                int cur = q.front(); q.pop();
                if (cur == 0) return res;
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < n; ++j) {
                        int next = cur;
                        for (auto dir : dirs) {
                            int x = i + dir[0], y = j + dir[1];
                            if (x < 0 || x >= m || y < 0 || y >= n) continue;
                            next ^= 1 << (x * n + y);
                        }
                        if (!visited.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                }
            }
            ++res;
        }
        return -1;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1284

类似题目:

Minimum Operations to Remove Adjacent Ones in Matrix

Remove All Ones With Row and Column Flips

Remove All Ones With Row and Column Flips II

参考资料:

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/discuss/446342/JavaPython-3-Convert-matrix-to-int%3A-BFS-and-DFS-codes-w-explanation-comments-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation