(nice!!!)(LeetCode) 3240. 最少翻转次数使二进制矩阵回文 II (分类讨论、数组)

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

思路：分类讨论，需要对行和列的个数进行讨论，时间复杂度为0(nm)，细节看注释。

C++版本：

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int ans=0;
        int n=grid.size(),m=grid[0].size();
        //当行和列都为偶数时
        for(int i=0;i<n/2;i++){
            for(int j=0;j<m/2;j++){
            	//只需让对应四个角位置上的数保持一致
                int ct=grid[i][j]+grid[n-i-1][j]+grid[i][m-j-1]+grid[n-i-1][m-j-1];
                //因为1的个数要被4整除，在此前提下最少翻转次数为min(ct,4-ct)
                ans+=min(ct,4-ct);
            }
        }
        //当行和列都为奇数时，中间位置必须是0
        if(n%2&&m%2) ans+=grid[n/2][m/2];
        //ct1来记录当行和列为奇数时，相同的前提下1的个数。
        //res来记录当行和列为奇数时，不同时，需要进行修改的次数。
        int ct1=0,res=0;
        //奇数行
        if(n%2){
            for(int j=0;j<m/2;j++){
                if(grid[n/2][j]==grid[n/2][m-j-1]) ct1+=grid[n/2][j]*2;
                else res++;
            }
        }
        //奇数列
        if(m%2){
            for(int i=0;i<n/2;i++){
                if(grid[i][m/2]==grid[n-i-1][m/2]) ct1+=grid[i][m/2]*2;
                else res++;
            }
        }
        //先把要修改的次数加上
        ans+=res;
        //如果ct1的个数不能被4整除，且res为0时，就需要将一对1修改为0。而res不为0时，将一个0修改为1即可。剩余的res-1都修改为0。
        if(ct1%4&&res==0) ans+=2;

        return ans;
    }
};

JAVA版本：

class Solution {
    public int minFlips(int[][] grid) {
        int ans=0;
        int n=grid.length,m=grid[0].length;
        //当行和列都为偶数时
        for(int i=0;i<n/2;i++){
            for(int j=0;j<m/2;j++){
            	//只需让对应四个角位置上的数保持一致
                int ct=grid[i][j]+grid[n-i-1][j]+grid[i][m-j-1]+grid[n-i-1][m-j-1];
                //因为1的个数要被4整除，在此前提下最少翻转次数为min(ct,4-ct)
                ans+=Math.min(ct,4-ct);
            }
        }
        //当行和列都为奇数时，中间位置必须是0
        if(n%2==1&&m%2==1) ans+=grid[n/2][m/2];
        //ct1来记录当行和列为奇数时，相同的前提下1的个数。
        //res来记录当行和列为奇数时，不同时，需要进行修改的次数。
        int ct1=0,res=0;
        //奇数行
        if(n%2==1){
            for(int j=0;j<m/2;j++){
                if(grid[n/2][j]==grid[n/2][m-j-1]) ct1+=grid[n/2][j]*2;
                else res++;
            }
        }
        //奇数列
        if(m%2==1){
            for(int i=0;i<n/2;i++){
                if(grid[i][m/2]==grid[n-i-1][m/2]) ct1+=grid[i][m/2]*2;
                else res++;
            }
        }
        //先把要修改的次数加上
        ans+=res;
        //如果ct1的个数不能被4整除，且res为0时，就需要将一对1修改为0。而res不为0时，将一个0修改为1即可。剩余的res-1都修改为0。
        if(ct1%4!=0&&res==0) ans+=2;
        return ans;
    }
}