← 返回题目列表

Codeforces · 961/C

C. 棋盘

中文机器翻译题面 查看原题

马格努斯决定玩一个经典的国际象棋游戏。虽然他在储物柜里看到的东西让他震惊了!他最喜欢的棋盘被分成了 4 块,每块的大小为 n × n,n 总是奇数。更糟糕的是,有些方块的颜色是错误的。第 k 块棋盘的第 i 行第 j 个方格的颜色为 ak, i, j; 1 为黑色,0 为白色。

现在马格努斯想要改变一些方格的颜色,以便他重新着色最小数量的方格并从有效的棋盘中获得棋子。每个方格的颜色都与有效棋盘中相邻方格的颜色不同。它的大小应该是 2n x 2n。您可以移动棋子,但不允许旋转或翻转它们。

输入

第一行包含奇数 n (1 ≤ n ≤ 100) — 棋盘上所有棋子的大小。

接下来是 4 段,每段描述一块板。每行由 n 行 n 个字符组成;如果方块最初是黑色的,则第 i 行的第 j 行等于 1,否则等于 0。段之间用空行分隔。

输出

打印一个数字——Magnus 应该重新着色才能获得有效棋盘的最小方块数。

示例

输入 #1

1
0
0
1
0

输出 #1

1

输入 #2

3
101
010
101
101
000
101
010
101
011
010
101
010

输出 #2

2