Решение задачи "Шахматная доска" с Codeforces

С пояснением Просмотров: 11

Однажды Магнус решил разыграть одну классическую шахматную партию. Но открыв чулан, Магнус пришел в ужас! Его любимая доска была разломлена на 4 части, каждая размера n на n, причем n обязательно нечетно. Хуже того, некоторые клетки имели неправильный цвет. j-я клетка i-й строки k-й части доски имеет цвет a k, i, j; 1 соответствует черному цвету, а 0 — белому.

Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
string a[4][N];

int main() {
	cin >> n;
	for(int k = 0; k < 4; ++k)
		for(int i = 0; i < n; ++i){
			cin >> a[k][i];
				for(int j = 0; j < n; ++j)
			    a[k][i][j] -= '0';
		}
	
	vector <int> v;
	for(int k = 0; k < 4; ++k){
		int sum = 0;
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
				if((i + j) % 2 != a[k][i][j])
					++sum;
		v.push_back(sum);
	}
	
	int res = int(1e9);
	vector <int> perm;
	for(int k = 0; k < 4; ++k) perm.push_back(k);
	do{
		int sum = 0;
		for(int k = 0; k < 4; ++k){
			int id = perm[k];
			if(k & 1)
				sum += v[id];
			else
				sum += n * n - v[id];
		}
		
		res = min(res, sum);
	}while(next_permutation(perm.begin(), perm.end()));

	cout << res << endl;
}