- Leetcode 3240. Minimum Number of Flips to Make Binary Grid Palindromic II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3240. Minimum Number of Flips to Make Binary Grid Palindromic II
1. 解题思路
这一题的话要同时满足行列上都是回文，因此我们每次考察需要考虑四个角上对应的元素，考察通过最少次数的变换使之变得都相同，显然如果他们本身相同，那么不变即可，如果有三个元素相同，变剩下那个即可，如果有两个元素相同，随机变两个即可。且变换之后的1的个数总是4的倍数。
唯一需要额外考虑的是中间行，中间列以及中心元素。对于中心行以及中间列，我们只需要考察单一行或列上的成对元素即可，将其变为回文并不复杂，只是需要额外讨论下变换之后的1的个数，如果原本已构成回文的1的个数为不为4的倍数，仅为2的倍数，且没有其他数字需要变动，则需要额外加两次变换使之总的1的个数为4的倍数。至于最中心的元素，则必须使其为0才能保证4的倍数条件。
最后，我们统计一下总的flip次数即可。
2. 代码实现
给出python代码实现如下：
class Solution:def minFlips(self, grid: List[List[int]]) -> int:n, m = len(grid), len(grid[0])ans = 0for i in range(n//2):for j in range(m//2):s = grid[i][j] + grid[n-1-i][j] + grid[i][m-1-j] + grid[n-1-i][m-1-j]if s == 1 or s == 3:ans += 1elif s == 2:ans += 2cnt, changed = 0, 0if n % 2 == 1:for j in range(m // 2):s = grid[n//2][j] + grid[n//2][m-1-j]if s == 1:changed += 1ans += 1else:cnt += sif m % 2 == 1:for i in range(n//2):s = grid[i][m//2] + grid[n-1-i][m//2]if s == 1:changed += 1ans += 1else:cnt += sif cnt % 4 == 2 and changed == 0:ans += 2if n % 2 == 1 and m % 2 == 1:ans += grid[n//2][m//2]return ans
提交代码评测得到：耗时2341ms，占用内存70.4MB。