Codeforces 961C Chessboard（将碎了的、染色乱了的棋盘碎片拼一起）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：点击打开链接

Magnus decided to play a classic chess game. Though what he saw in his locker shocked him! His favourite chessboard got broken into 4pieces, each of size n by n , n is always odd. And what's even worse, some squares were of wrong color. j -th square of the i -th row of k -th piece of the board has color a k , i , j ; 1 being black and 0 being white.

Now Magnus wants to change color of some squares in such a way that he recolors minimum number of squares and obtained pieces form a valid chessboard. Every square has its color different to each of the neightbouring by side squares in a valid board. Its size should be 2 n by 2 n . You are allowed to move pieces but not allowed to rotate or flip them.

Input

The first line contains odd integer n (1 ≤ n ≤ 100) — the size of all pieces of the board.

Then 4 segments follow, each describes one piece of the board. Each consists of n lines of n characters; j -th one of i -th line is equal to 1 if the square is black initially and 0 otherwise. Segments are separated by an empty line.

Output

Print one number — minimum number of squares Magnus should recolor to be able to obtain a valid chessboard.

Examples

input

Copy

output

input

Copy

output

题目大意：问最少染多少色，可以将四块拼成一个完整的国际象棋棋盘

思路：四块碎片是无序的，随便以什么顺序拼，只要能完成一块棋盘就行

定义模式一：棋盘碎片的第一格为1，如样例二中的第一块碎片

定义模式二：棋盘碎片的第一格为0，如样例二中的第四块碎片

显然 一个完整的棋盘应该是由两块模式一、两块模式二组成的

于是我们只需要求出每块碎片变成模式一、变成模式二需要的染色数，然后暴力枚举哪两块碎片变成模式一（另外两块碎片变成模式二）总共需要的染色数最少，就行了

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<set>

#include<queue>

#include<cmath>

typedef long long ll;

using namespace std;

const ll maxn = 1e6 + 10;

char a[105][105];

int m1[4], m2[4];

int main(){

    int n;

    memset(m1, 0, sizeof(m1));

    memset(m2, 0, sizeof(m2));

    scanf("%d",&n);

    getchar();

    for(int i = 0 ; i < 4 ; i++){

    	for(int j = 0; j < n ;j++){

    		scanf("%s", a[j]);

    		for(int k = 0; k < n; k++){

    			if((j+k)%2==0){

    				if(a[j][k]-'0' == 1) m2[i]++;

    				else if(a[j][k] - '0' == 0) m1[i]++;

				}

				else if((j+k)%2==1){

					if(a[j][k]-'0' == 1)m1[i]++;

					else if(a[j][k] - '0' == 0) m2[i]++;

				}

			}

		}

	}

	int ans = n * n * 4;

	for(int i = 0; i < 3; i++){//第i和j个棋盘碎片作为模式一，其他两个模式二

		for(int j = i+1; j < 4; j++){

			int sum = 0;

			for(int k = 0; k < 4; k++){

				if(k!=i && k!=j)sum+=m2[k];

			}

			sum+=(m1[i]+m1[j]);

			//cout << sum << endl;

			ans = min(ans, sum);

		}

	}

	cout << ans << endl;

    return 0;

}