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

本文主要是介绍Leetcode3240. 最少翻转次数使二进制矩阵回文 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

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

解法1：分类讨论

在这里插入图片描述

特殊情况：

讨论正中间一排（如果 m 是奇数）和正中间一列（如果 n 是奇数）中的格子要如何翻转。

在这里插入图片描述

综上所述：

如果 diff>0，额外把 diff 加入答案。
如果 diff=0，额外把 cnt1 mod4 加入答案。

代码：

/** @lc app=leetcode.cn id=3240 lang=cpp** [3240] 最少翻转次数使二进制矩阵回文 II*/// @lc code=start
class Solution
{
public:int minFlips(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;int ans = 0;for (int i = 0; i < m / 2; i++)for (int j = 0; j < n / 2; j++){int cnt1 = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];ans += min(cnt1, 4 - cnt1); // 全为 1 或全为 0}if (m % 2 && n % 2 && grid[m / 2][n / 2] == 1){// 正中间的数必须是 0ans++;}int diff = 0, cnt1 = 0;if (m % 2){// 统计正中间这一排for (int j = 0; j < n / 2; j++){if (grid[m / 2][j] != grid[m / 2][n - 1 - j])diff++;elsecnt1 += grid[m / 2][j] * 2;}}if (n % 2){// 统计正中间这一列for (int i = 0; i < m / 2; i++){if (grid[i][n / 2] != grid[m - 1 - i][n / 2])diff++;elsecnt1 += grid[i][n / 2] * 2;}}if (cnt1 % 4 == 0){// 把这 diff 对数全部变成 0ans += diff;}else{if (diff){// 把一对数都变成 1，其余全变成 0，要翻转 diff 个数ans += diff;}else{// 把两个 1 翻转为 0ans += 2;}}return ans;}
};
// @lc code=end