cf Educational Codeforces Round 41 C. Chessboard

本文主要是介绍cf Educational Codeforces Round 41 C. Chessboard，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
C. Chessboard
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Magnus decided to play a classic chess game. Though what he saw in his locker shocked him! His favourite chessboard got broken into 4 pieces, 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 ak, 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 2n by 2n. 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
1
0

0
output
1
input
3
101
010
101

101
000
101

010
101
011

010
101
010
output
2

中文：

给你一个n×n的棋盘，这个棋盘碎成4份，每份大小相同，每份的尺寸都是n，而且是奇数。现在给你这四份碎的棋盘问你组成原来的棋盘最少修改多少个方格（就是0改成1或者1改成0），原来的棋盘就是一个1和0交替出2n×2n的01矩阵。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include <string>
#include <set>
#include<vector>
using namespace std;
int n,mark[4][2];string s1, s2, s3, s4,s;int main()
{ios::sync_with_stdio(false);while (cin >> n){s1.clear();s2.clear();s3.clear();s4.clear();memset(mark, 0, sizeof(mark));for (int i = 1; i <= n; i++){cin >> s;s1 += s;}for (int i = 1; i <= n; i++){cin >> s;s2 += s;}for (int i = 1; i <= n; i++){cin >> s;s3 += s;}for (int i = 1; i <= n; i++){cin >> s;s4 += s;}for (int i = 0; i < n*n; i++){if (i % 2){if (s1[i] == '0')mark[0][0]++;elsemark[0][1]++;if (s2[i] == '0')mark[1][0]++;elsemark[1][1]++;if (s3[i] == '0')mark[2][0]++;elsemark[2][1]++;if (s4[i] == '0')mark[3][0]++;elsemark[3][1]++;}else{if (s1[i] == '1')mark[0][0]++;elsemark[0][1]++;if (s2[i] == '1')mark[1][0]++;elsemark[1][1]++;if (s3[i] == '1')mark[2][0]++;elsemark[2][1]++;if (s4[i] == '1')mark[3][0]++;elsemark[3][1]++;}}int ans = INT_MAX;for (int i = 0; i < 4; i++){for (int j = i + 1; j < 4; j++){for (int x = 0; x < 4; x++){for (int y = x + 1; y < 4; y++){if (x != i&&x != j&&y != i&&y != j){ans = min(ans, mark[i][0] + mark[j][0] + mark[x][1] + mark[y][1]);}}}}}cout << ans << endl;}return 0;
}