题目大意
给出一个nnn,nnn必然是偶数。 同时给出一个n×nn \times nn×n的矩阵,你要保证这个矩阵翻转90°90°90°之后,每个位置上的字符不发生变化。你可以对矩阵当中任意一个字符进行字典序+1的操作。
题目目的
求达成完美矩阵的最少操作次数
算法与时间
不难可以推理出,在一个必然为正方形的矩阵上面,如果进行翻转360°,每个位置的字符能够到达的地方是一致的。
举个例子,假如矩阵为
枚举其中几个字符坐标旋转发生的变化为
1,1−>1,4−>4,4−>4,1−>1,11,1 -> 1,4 -> 4,4 -> 4,1 -> 1,11,1−>1,4−>4,4−>4,1−>1,1
1,2−>2,4−>4,3−>3,1−>1,21,2 -> 2,4 -> 4,3 -> 3,1 -> 1,21,2−>2,4−>4,3−>3,1−>1,2
然后我们便可以推理出,四个字符必须保持一致,才可以让矩阵旋转后保持不变。
同时题目要求只能+1的操作,那么意味着你只能将某一个字符往前+1,而不能往后-1,这就规避掉了我们在四个字符当中选取中间值进行操作的情况。那么根据最优选择,那便是选择四个字符当中字典序最大的作为标准,然后进行统一。
那么我们可以把这个矩阵分为四部分(因为n一定为偶数),遍历其中第一部分的每一个字符,枚举旋转90°后其他三个字符的坐标即可。
难点是在怎么计算坐标,其实根据上面的例子,我们就可以发现了。
我们设置当前处于第i行,第j列(下标从1开始),然后来列公式,通过观察(1,2)可得知
第一个坐标为i,ji,ji,j 第二个坐标为j,n−i+1j,n-i+1j,n−i+1,第三个坐标n−i+1,n−j+1n-i+1,n-j+1n−i+1,n−j+1,第四个坐标n−j+1,in-j+1,in−j+1,i
我们会发现,每个坐标的行下标相当于前一个坐标的列下标,列下表相当于N减去前一个坐标的行下表+1.
推理出四个方向的坐标后,根据只能往前挪动一格的条件,我们就可以的得出每项的通项公式为
max(第一个坐标的字符,第二个坐标的字符,第三个坐标的字符,第四个坐标的字符)−剩余其他坐标的字符max(第一个坐标的字符,第二个坐标的字符,第三个坐标的字符,第四个坐标的字符) - 剩余其他坐标的字符max(第一个坐标的字符,第二个坐标的字符,第三个坐标的字符,第四个坐标的字符)−剩余其他坐标的字符 即可得到四个位置字符一致的操作次数。
代码示范