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

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。

思路：

首先，考虑回文字符的特点，对称行，列均相等，因此对于对应的两行，两列，一共四条线构成一个口字形，在化成回文后一定是有%4等于0个1，可以想成左上角，右下角，左下角，右上角对应四个，因此模4一定为0，因此对于这些位置，只需要考虑用最小次数翻转成回文就行，1的个数%4等于0一定恒满足。

然后，对于空出来的那一行或者一列（如果行或列是奇数的时候才会有这种情况），还需要额外处理这一行或者列的元素，此处以行为例子说明，列的做法同理。对于行k，需要处理每一列上这一行所在的元素，记录对应位置元素不相等的个数和元素相等且为1的个数，因为这些会对于最后1的个数产生影响，而相等且均为0的对于位置不会对1的个数有影响因此不用记录。假设对应位置不同的情况有diff个，对应相同且为1的元素个数是cnt1个，则如果diff==0时，只需要根据cnt1的情况进行处理就好，具体处理情况就是看cnt1%4的值，如果是2就翻转两个1变成0，如果是零已经满足无需变换。如果diff不为0，那么满足1的个数%4==0的最小翻转方法就是翻转diff次，因为翻转diff次绝对可以使得当前1的个数%4==0，比如diff等于1时，当前1的个数一定是奇数个，是1或者3，是1就将1翻转成0，是3就将0翻转成1，对于大于diff的情况，只需要一个按照上述翻转方法，其余无脑变成0就一定满足1的个数%4==0.

最后考虑特殊情况，如果行/列都是奇数的时候，会出现中心位置额外多出来一个元素，这个元素没有对应的匹配元素，因此只能变成0才行，因为如果是1，最后回文串中1的个数一定是奇数无法满足%4==0的条件。

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
         int m=grid.size(),n=grid[0].size();
         int ans=0;
         for(int i=0;i<m/2;i++)
         for(int j=0;j<n/2;j++)
         {
            int cnt=grid[i][j]+grid[i][n-j-1]+grid[m-i-1][j]+grid[m-i-1][n-j-1];
            ans+=min(cnt,4-cnt);
         }
         int diff=0,cnt1=0;
         if(m&1)
         {
             for(int i=0;i<n/2;i++)
             if(grid[m/2][i]==grid[m/2][n-1-i])
             cnt1+=2*grid[m/2][i];
             else diff++;
         }
            if(n&1)
         {
             for(int i=0;i<m/2;i++)
             if(grid[i][n/2]==grid[m-1-i][n/2])
             cnt1+=2*grid[i][n/2];
             else diff++;
         }
         if(m&1&&n&1)
         {
            ans+=grid[m/2][n/2];
         }
         
          if (diff > 0) {
            ans += diff;//哪怕只有一个diff，对于当前i%4的情况只有可能是1或者3，那么一定可以变成%4等于0
        } else {
            ans += cnt1 % 4;
        }
         return ans;

    }
};