Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

题目

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 neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

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

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

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 don't need to change it.

Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6
Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Constraints:

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

解题报告

理解题意

• 给定一个数组 m * n
• 数字只有 0 或者 1
• flip 时必须：五个相邻数字（自己、上、下、左、右）。
• 目标状态为全部为 0

理解例子

例子 1

• S：[[0, 0], [0, 1]]
• 结果：3

0	0
0	1

思路

• 看到题目应该就会反映到会使用BFS来解决问题：（每次拓展上下左右和自己）
• 每次拓展的时候回尝试将周边的数字进行翻转
• 终止状态：找到全0、全部遍历完毕，并且记录步数。
• 因为只有0/1两个数字。因此可以考虑使用状态压缩来将二维数组进行降维。
• 考虑将例子中的二维数组：[[0,0],[0,1]] —> [0001],这样时间复杂度就会缩短。

划分

• 可以把划分想象成两个部分，左边和右边。
• 左边：是从 0…j 进行 k-1 次的划分。右边： 一次划分（）。
• dp_[i][k] = min{dp_[i][k], dp_[j][k-1] + dp_change[j][i]}
• dp_change[j][i] 表示从j到i 的最小更换次数。

更改字符

• 如果划分确定后，如何更改字符就比较好确定了
• 回文字符串应该从中间开始构建，并且向两边拓展
• 如果前后两个字符相等(str[i] == str[j]): dp_change[i][j] = dp_change[i+1][j-1]
• 如果前后两个字符不等(str[i] != str[j]): dp_change[i][j] = 1 + dp_change[i+1][j-1]
• dp_change[i][j] = (str[i] != str[j]) + dp_change[i+1][j-1]

解决了以上两个问题，那完整的问题，就解决了

流程

• 异常判断
• 针对所有的位置，尝试所有的分割，

伪代码

int palindromePartition(string &str, int k){

}

代码

class Solution {
public:
    int findMediaSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        const int m = nums1.size();
        const int n = nums2.size();
        if (m > n) return findMediaSortedArrays(nums2, nums1);

    }
};

时间复杂度

如一开始分析：时间复杂度：线性时间 \(\mathcal{O(n)}\)

空间复杂度

额外申请了和一个链表，因此空间复杂度也为 \(\mathcal{O(max(len(l1), len(l2)))}\)