魏老四OJ
Home
ProblemSet
Source/Category
Contest
题单
Status
Ranklist
F.A.Qs
Login
2331: C.正方形(square)
Memory Limit:128 MB
Time Limit:1.000 S
:
Creator:
Submit:25
Solved:7
Submit
Statistics
Description
有一个边长为 2n − 1 的正方形方格,包含有 (2n − 1) × (2n − 1) 个格子,每个格子里面是0, 1, 2 三种数字中的一种。现在想通过修改某些位置上的数字,把正方形方格变为好看的,好看的标准如下:
1. 每一圈都是同一个数字。
2. 每个数字至少有一圈,而且由外到内依次是 2, 1, 0 。
问:至少修改多少个数字才能把原来的正方形方格变为好看的正方形方格。
Input
第 1 行 1 个整数 n 。
接下来的 2n − 1 行,每行 2n − 1 个整数,中间用一个空格隔开。
Output
输出 1 行 1 个整数,表示把原来正方形方格变为好看的,最少需要修改多少个方格中的数字。
Sample Input
3 1 1 2 1 2 2 0 1 1 0 0 0 1 0 1 2 2 2 1 2 0 2 1 1 0
Sample Output
16
HINT
样例1解释:
如图所示,需要修改的方格有 16 个。
样例2解释:
最少修改 48 次将正方形方格变为好看的。最终正方形方格由外向内,第 1 圈是 2 ,第 2, 3 圈是1 ,其余都是 0 。
数据范围:
对于 30% 的数据, n ≤ 30 ;
对于 60% 的数据, n ≤ 100 ;
对于 100% 的数据, n ≤ 500 。
Source/Category
2023年青岛市程序设计竞赛试题(小学组)
Submit
Statistics