本题要求求出最少的增加操作次数,使得网格在顺时针旋转 0∘、90∘、180∘、270∘ 后完全相同。由于每次只能将某个格子的数值增加 1,要想使若干格子最终相等,最优的做法是将它们全部增加到当前的最大值,所需操作次数即为 ∑(最大值−当前值)。
关键观察:旋转四次对应一组格子。对于网格中的任意位置 (x,y)(行列编号从 0 开始),顺时针旋转 90∘ 后的新坐标为 (y,n−1−x)。连续旋转四次会回到起点,因此除了 n 为奇数时的正中心格子单独成一组(大小为 1),其余所有格子都可以按旋转轨道分成大小为 4 的组。
算法步骤如下:
给定一个 n×n 的网格,每个格子中有一个正整数。你可以进行任意次操作:每次选择一个格子,将其数值增加 1。目标是使网格满足“四次旋转对称”性质:将网格顺时针旋转 0∘、90∘、180∘、270∘ 后,得到的网格完全相同。请问最少需要进行多少次操作?
约束条件:网格的行数和列数 n 满足 1≤n≤100。每个格子的初始数值均为不超过 109 的正整数。
第一行包含一个整数 n (1≤n≤100),表示网格的大小。 接下来 n 行,每行包含 n 个整数,表示对应格子的初始数值。每个数值均为不超过 109 的正整数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册