锐客网

  1. 首页 > it技术 > >

C. Chessboard time limit per test1 second memory limit per test256 megabytes inputstandard input out

思维

C. Chessboard time limit per test 1 second memory limit per test 256 megabytes input standard input output standard 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 Copy

1 0010

output
1

input Copy
3 101 010 101101 000 101010 101 011010 101 010

output
2


这个题感觉蛮有意思，四块棋盘，每个格子或者是0或者是1，让你把四个长为奇数的棋盘合成一个棋盘，顺序不计，问你最少1修改几个格子，使得每个格子与相邻的格子数字不同。
我们先想想，正确的棋盘是什么样子那？ 无非是1个0,1个1交替出现，与坐标联系起来，i+j 为奇数则为 某个状态，否则为另一个状态。其实一个完整的棋盘分成四个，再把它合起来，能产生两种棋盘，第一个为0 或者第一个为 1.
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; char s[4][150][150]; char mp[250][250]; int ii[] = {0,1,2,3}; int n; int main() { cin >> n; for(int i = 0; i < 4; i++) for(int j = 0; j < n; j++) for(int k = 0; k < n; k++) cin >> s[i][j][k]; int ans = 1e8; do{ int tmp = 0; for(int i = 0; i < 2*n; i++) for(int j = 0; j < 2*n; j++) { if(i <= n && j <= n) { mp[i][j] = s[ii[0]][i][j]; } if(i <= n && j > n) { mp[i][j] = s[ii[1]][i][j-n]; } if(i > n && j <= n) { mp[i][j] = s[ii[2]][i-n][j]; } if(i > n && j > n) { mp[i][j] = s[ii[3]][i-n][j-n]; } char c = (i+j) % 2 ? '1' : '0'; if(c != mp[i][j]) tmp++; } ans = min(ans,tmp); }while(next_permutation(ii,ii+4)); cout << ans <


【C. Chessboard time limit per test1 second memory limit per test256 megabytes inputstandard input out】

    推荐阅读


    上一篇：java|java环境变量配置

    下一篇：每周成长回顾20170219