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.
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.
Print one number — minimum number of squares Magnus should recolor to be able to obtain a valid chessboard.
1
0
0
1
0
1
3
101
010
101
101
000
101
010
101
011
010
101
010
题意，现在有2n*2n的棋盘，被分成了n*n的四个部分，现在可以以任意的顺序拼回原来的棋盘
然后需要进行操作将棋盘变得相邻的方格的数字不同，每次操作可以将一个0变成1，或者0变成1
问最少需要多少此操作
分析：棋盘拼接的方式有24种，所以可以直接枚举所有的拼接方式。
对于每种拼接方式完成后，用dp[i][j][k] 表示拼接到i行j列,且该方格的数字为k时所消耗的操作数
则有转移方程如下（r为该方格最初的颜色）
dp[i][j][r]=dp[i-1][j][r^1]+dp[i][j-1][r^1]-dp[i-1][j-1][r];
dp[i][j][r^1]=dp[i-1][j][r]+dp[i][j-1][r]-dp[i-1][j-1][r^1]+1;
代码如下:
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; #define INF 0x3f3f3f3f int map1[220][220]; int dp[220][220][2]; int n; int nn; int minn=INF; int str[5][220][220]; char ch; int x[5]={0,1,2,3,4}; void trans(int a,int b,int c,int d) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map1[i][j]=str[a][i][j]; for(int i=1;i<=n;i++) for(int j=n+1;j<=nn;j++) map1[i][j]=str[b][i][j-n]; for(int i=n+1;i<=nn;i++) for(int j=1;j<=n;j++) map1[i][j]=str[c][i-n][j]; for(int i=n+1;i<=nn;i++) for(int j=n+1;j<=nn;j++) map1[i][j]=str[d][i-n][j-n]; } void solve() { for(int i=0;i<=nn;i++) { for(int k=0;k<=1;k++) { dp[i][0][k]=0; dp[0][i][k]=0; } } dp[1][1][map1[1][1]]=0; dp[1][1][1^map1[1][1]]=1; for(int i=1;i<=nn;i++) for(int j=1;j<=nn;j++) { if(i==1&&j==1)continue; int r=map1[i][j]; dp[i][j][r]=dp[i-1][j][r^1]+dp[i][j-1][r^1]-dp[i-1][j-1][r]; dp[i][j][r^1]=dp[i-1][j][r]+dp[i][j-1][r]-dp[i-1][j-1][r^1]+1; } minn=min(dp[nn][nn][0],minn); minn=min(dp[nn][nn][1],minn); } int main() { scanf("%d",&n); nn=2*n; for(int k=1;k<=4;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf(" %c",&ch); str[k][i][j]=ch-'0'; } int num=0; do { trans(x[1],x[2],x[3],x[4]); solve(); num++; }while(next_permutation(x+1,x+5)); printf("%d ",minn); return 0; }