目标
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。
示例 1：
输入：grid = [[1,0,0],[0,1,0],[0,0,1]]
输出：3示例 2：
输入：grid = [[0,1],[0,1],[0,0]]
输出：2
示例 3：
输入：grid = [[1],[1]]
输出：2说明：
- m == grid.length
- n == grid[i].length
1 <= m * n <= 2 * 10^50 <= grid[i][j] <= 1
思路
有一个二进制矩阵 grid，每次操作可以翻转任意格子，使 0 变为 1，或者使 1 变为 0。求使得矩阵 所有行 和 所有列 变成回文，且矩阵中 1 的数目可以被 4 整除 的最少操作次数。
考虑矩阵操作后的最终状态，类似一个 田 或者 日 或者 旋转 90 度的 日 字，每一个 口 内的元素完全相同，中间线上如果有元素的话也是对称的。
昨天的题 最少翻转次数使二进制矩阵回文I 要求的是 所有行 或者 所有列，当我们保证行是回文的时候，如果遇到不同的元素，翻转哪一个都可以。对于本题，需要同时保证列也是回文的，并且矩阵中 1 的个数能够被 4 整除。在要求操作次数最小的情况下，选择翻转哪一个是有影响的。需要考虑翻转元素后的代价，如果我们在保证 行 是回文的时候翻转了某个元素导致了该元素所在 列 的对称位置上的元素不同，那么翻转次数需要多加1，而如果翻转镜像位置的元素刚好可以使所在列对称位置上的元素相同，应该优先选择。实际上矩阵中 1 的数目可以被 4 整除，只需考虑奇数行与奇数列时的中间行与中间列，因为在其它区域出现 1，如果行列是回文的，一定可以被 4 整除。
我们再重新梳理一下，翻转的时候优先选择代价最小的，只需要考虑 四个对称位置上的值哪个占少数就翻转哪个。分别统计中间行与列中 1 的个数，以及变成回文的操作次数。由于中间行、列的翻转是任意的，我们可以计算中间行列中 1 的个数之和 midOneCnt，注意这里需要去除中心元素（即行或列为奇数时的中间元素）后面单独处理。根据 mod = midOneCnt % 4 的值，我们可以确定操作翻转哪个元素：
- 如果值为
1，将1置0 - 如果值为
2，都行 - 如果值为
3，将0置1
需要的操作次数为 Math.min(mod, 4 - mod)。如果保证回文的操作的次数不够使 1 的个数满足条件，就需要额外的操作。注意，这么做的前提条件是 有足够的格子，如果中线的格子总数不够 4 个，比如 3 个格子，里面都是 1 需要补一个 1 是无法操作的，这时操作次数只能取 mod 了。
最后考虑中心元素，它必须为0，否则 1 的总个数不可能被 4 整除。
代码
/**
* @date 2024-11-15 11:28
*/
public class MinFlips3240 {
/**
* 执行通过
*/
public int minFlips(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
int rowMid = m / 2;
int colMid = n / 2;
for (int i = 0; i < rowMid; i++) {
for (int j = 0; j < colMid; j++) {
int jj = n - j - 1;
int ii = m - i - 1;
int sum = grid[i][j] + grid[i][jj] + grid[ii][j] + grid[ii][jj];
// 取四个元素中的少数元素个数
res += Math.min(sum, 4 - sum);
}
}
int midRowOneCnt = 0;
int midRowOptCnt = 0;
// 计算奇数行时中间行的操作次数与1的个数
if (m % 2 == 1) {
for (int j = 0; j < colMid; j++) {
int jj = n - j - 1;
midRowOneCnt += grid[rowMid][j] + grid[rowMid][jj];
midRowOptCnt += grid[rowMid][j] ^ grid[rowMid][jj];
}
}
int midColOneCnt = 0;
int midColOptCnt = 0;
// 计算奇数列时中间列的操作次数与1的个数
if (n % 2 == 1) {
for (int i = 0; i < rowMid; i++) {
int ii = m - i - 1;
midColOneCnt += grid[i][colMid] + grid[ii][colMid];
midColOptCnt += grid[i][colMid] ^ grid[ii][colMid];
}
}
int midOpt = midRowOptCnt + midColOptCnt;
res += midOpt;
int midOneCnt = midRowOneCnt + midColOneCnt;
int mod = midOneCnt % 4;
int remainder;
// 确保格子数量足够
if (m + n <= 4) {
remainder = midOpt - mod;
} else {
remainder = midOpt - Math.min(mod, 4 - mod);
}
// 如果操作次数不够需要补上
if (remainder < 0) {
res += -remainder;
}
// 处理中心元素
if (m % 2 == 1 && n % 2 == 1) {
res += grid[rowMid][colMid];
}
return res;
}
}
性能
