JZX轻语：简

LeetCode 3240 - 最少翻转次数使二进制矩阵回文 II

发表于2024年08月09日

在3239的基础上，条件升级为行回文且列回文，且1的次数必须被4整除。分析可知，由于两种方向都对称，每个元素都可能会有3个镜像位置，也就是题目中为什么要求能被4整除: 无论该位置是0还是1，通过翻转满足题目要求后，这四个位置要么全0，要么全1，1的个数都会被4整除。这样就解决了吗？并不是！我们还需要考虑奇数行和奇数列的情况：

如果行数和列数都是奇数，那么中心位置必须为0，否则1的个数不可能被4整除。
如果行或列为奇数，我们需要考虑中心行和中心列: 在中心行/列中，除了最中央的元素(只有行和列都为奇数的时候，才会有这个元素)外，每个元素有1个镜像位置。我们可以统计中央行和列的1的个数，以及不对称的位置对个数。然后使用贪心的方法计算最少翻转次数: 首先考虑保证对称的情况，此时需要翻转的次数为不对称位置对的个数；然后再考虑能被4整除的情况，此时需要翻转的次数为min(4, 4 - (1的个数 % 4))。我们需取两种情况的最大值即可保证两种情况都能满足！

证明为啥取最大值即可：首先证明情况1和情况2的翻转次数的奇偶性是一样的：首先，如果某个对称位置对的数字是一样的，则要么全0，要么全1，这些已经保持对称的位置对集合中，0和1的个数为偶数。而不对称的位置对中，必定恰好有一个为0，有一个为1，所以此时这些集合中0和1的个数恰好为不对称位置对数。

如果情况1的翻转次数比情况2多：
- 如果情况2的翻转策略为0 -> 1，对于每个不对称位置对，我们可以将其中的0翻转为1，优先保证1的计数能被4整除。此时，由于两种情况的翻转次数奇偶性相同，所以情况1剩余的翻转次数必定为偶数，此时可以交替翻转（一个对0 -> 1；另一个对1 -> 0, …），能保证使得1的计数不会变化！
- 如果情况2的翻转策略为1 -> 0，雷同。
如果情况2的翻转次数比情况1多，不难得知，情况2的翻转次数只会有0, 1, 2，如果为1，根据奇偶性相同，情况1所需翻转次数必然也为1，此时根据情况2的策略，对那个不对称位置对进行相应翻转即可；如果为2，则情况1的翻转次数要么为0，要么为2。如果为0，随便选一个已经对称的位置对，全都改为0或1即可；如果为2，则该两个不对称位置对都按照情况1的策略进行翻转即可。

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        # 先遍历有3个镜像位置的情况
        for i in range(m // 2):
            for j in range(n // 2):
                one_cnt = (
                    grid[i][j] +
                    grid[m - i - 1][j] +
                    grid[i][n - j - 1] +
                    grid[m - i - 1][n - j - 1]
                )
                ans += min(one_cnt, 4 - one_cnt)
        # 处理中心位置
        if m % 2 and n % 2:
            ans += grid[m // 2][n // 2] == 1
            grid[m // 2][n // 2] = 0
        # 处理中心行和列
        one_cnt = 0
        rev_pair_cnt = 0
        if m % 2:  # 有中心行
            one_cnt += sum(grid[m // 2][j] for j in range(n))
            rev_pair_cnt += sum(grid[m // 2][j] != grid[m // 2][n - j - 1] for j in range(n // 2))
        if n % 2:  # 有中心列
            one_cnt += sum(grid[i][n // 2] for i in range(m))
            rev_pair_cnt += sum(grid[i][n // 2] != grid[m - i - 1][n // 2] for i in range(m // 2))
        # 保证对称的最少翻转次数
        diff = one_cnt % 4
        diff = min(diff, 4 - diff)
        # 保证能被4整除的最少翻转次数为rev_pair_cnt
        # 两种情况取最大值
        return ans + max(diff, rev_pair_cnt)

2024/11/16更新：每日一题遇到了这道题，使用C++重新做了一遍。在处理中心行/列的时候，和上面的做法有点差异：统计不对称位置对的个数need_rev_pair_cnt和1对称位置对的个数one_pair_cnt。

如果1对称位置对的个数one_pair_cnt为奇数，且不对称位置对的个数need_rev_pair_cnt为0或者1（此时满足one_pair_cnt % 2 + need_rev_pair_cnt == 1）：则根据need_rev_pair_cnt的取值：
- 如果为0（即不存在不对称的位置对），则需要翻转2次（翻转1对称位置对中的其中一对为0）；
- 如果为1，则需要翻转1次（翻转不对称位置对中的0为1）；
否则（即one_pair_cnt + need_rev_pair_cnt > 1）：则只需要翻转need_rev_pair_cnt次（即只翻转不对称的位置对中的其中一员）即可。翻转策略如下：首先，优先翻转0为1，使得1的个数能被4整除；然后再翻转1为0。由于one_pair_cnt + need_rev_pair_cnt > 1，所以总能找到合适的策略。

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int ans = 0;
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m / 2; ++i) {
            for (int j = 0; j < n / 2; ++j) {
                int one_cnt = grid[i][j] + grid[m - 1 - i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][n - 1 - j];
                ans += min(one_cnt, 4 - one_cnt);
            }
        }

        if (m % 2 && n % 2 && grid[m / 2][n / 2]) { ++ans; grid[m / 2][n / 2] = 0; }
        int need_rev_pair_cnt = 0, one_pair_cnt = 0;
        if (m % 2) {
            for (int i = 0; i < n / 2; ++i) {
                if (grid[m / 2][i] != grid[m / 2][n - 1- i]) ++need_rev_pair_cnt;
                else if (grid[m / 2][i] == 1) ++one_pair_cnt;
            }
        } 
        if (n % 2) {
            for (int i = 0; i < m / 2; ++i) {
                if (grid[i][n / 2] != grid[m - 1 - i][n / 2]) ++need_rev_pair_cnt;
                else if (grid[i][n / 2] == 1) ++one_pair_cnt;
            }
        }

        if (one_pair_cnt % 2 + need_rev_pair_cnt == 1) {
            ans += need_rev_pair_cnt ? 1 : 2;
        } else {
            ans += need_rev_pair_cnt;
        }
        return ans;
    }
};

闪念标签：LC

题目链接：https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/