2015
09-17

Boring Game

Zero likes to play a boring game when he feels extremely boring. This his game proceeds in a square board with n rows and n column. Each grid in the board has either of two colors black or white. In each turn, Zero chooses a grid first. Let’s assume that the grid he chooses locates in the xth row and the yth column. And then, the neighbors which are existed of this grid (x + 1, y), (x �C 1, y), (x, y + 1), (x, y �C 1) and itself will convert their color into another. Till the end, Zero will transform the initial board to the goal board whose grids are all white. For instance, Here is the way to attain his goal. In his first turn, he selects (2, 2). And then he selects (1, 1) in the second turn. After that, he reaches his goal.

Zero reckons this mission, however, is too simple and naive. So he prefers to accomplish this assignment in minimal turns. He doesn’t know whether the turns he needs are the minimal turns, because of that he needs you to tell him the minimal turns of these initial boards.

There are several test cases in the input file. The first line of the input file contains an integer m(m <= 106), then m cases follow.
The first line of each test case contains an integer n(1 <= n <= 8), which is the length of a side of the square board.
Then the next line contains n integer a[i](0 <= a[i] <= 2n, 1 <= i <= n), which is the statement of the ith row respectively. The definition of a statement can be illustrated as n-length binary numbers, zero represents white and one represents black. For example, when n is equal to 4 and a[0] is equal to 5 = (0101)2, you can consider that the condition in the first line of this board is white, black, white, black.

There are several test cases in the input file. The first line of the input file contains an integer m(m <= 106), then m cases follow.
The first line of each test case contains an integer n(1 <= n <= 8), which is the length of a side of the square board.
Then the next line contains n integer a[i](0 <= a[i] <= 2n, 1 <= i <= n), which is the statement of the ith row respectively. The definition of a statement can be illustrated as n-length binary numbers, zero represents white and one represents black. For example, when n is equal to 4 and a[0] is equal to 5 = (0101)2, you can consider that the condition in the first line of this board is white, black, white, black.

2
3
4 3 2
4
1 0 0 0

2
-1

#include <iostream>
#include <cstring>
#include <cstdio>
//#define debug
using namespace std;

int a[30][30];
int x[80],n,equ,var;

void init()
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x[0])*30);
equ=n*n;
var=equ;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i!=0) a[i*n+j][(i-1)*n+j]=1;
if(i!=n-1) a[i*n+j][(i+1)*n+j]=1;
if(j!=0) a[i*n+j][i*n+j-1]=1;
if(j!=n-1) a[i*n+j][i*n+j+1]=1;
a[i*n+j][i*n+j]=1;
}
}
}

int Gauss()
{
int k,col,max_r;

for(k=0,col=0; k<equ&&col<var; k++,col++)
{
if(a[k][col]==0)
{
max_r=k;
for(int i=k+1; i<equ; i++)
if(a[i][col]>a[max_r][col])
{
max_r=i;
break;
}
if(max_r!=k)
for(int i=0; i<=var; i++)
swap(a[max_r][i],a[k][i]);
}
if(a[k][col]==0)
{
k--;
continue;
}
for(int i=k+1; i<equ; i++)
{
if(a[i][col])
for(int j=col; j<=var; j++)
a[i][j]=a[i][j]^a[k][j];
}
}
for(int i=k; i<equ; i++)
if(a[i][var]) return -1;

int lim=(1<<(var-k)),ans=100000;
for(int i=0; i<lim; i++)
{
int temp=i,sum=0;
for(int j=var-1; j>=k; j--)
{
x[j]=temp&1;
temp>>=1;
}
for(int j=k-1; j>=0; j--)
{
x[j]=a[j][var]&1;
for(int r=j+1; r<var; r++)
x[j]=x[j]^(a[j][r]&x[r]);
}
for(int j=0; j<var; j++)
sum+=x[j];
ans=min(ans,sum);
}
return ans;
}
int n2[4][2]=
{
3,2,3,1,2,3,1,3
};
int n3[9][3]=
{
5,1,6,0,2,7,5,4,3,1,3,1,
2,7,2,
4,6,4,
6,1,5,
7,2,0,
3,4,5
};
int n6[36][6]=
{
43,8,55,10,44,40,
3,20,53,17,14,4,
44,42,7,32,55,34,
13,21,56,1,59,17,
48,10,43,34,28,8,
53,4,59,20,13,5,
8,28,2,27,34,44,
20,54,5,59,21,14,
42,43,10,48,2,55,
21,53,20,3,16,59,
10,27,40,55,42,28,
4,14,16,54,17,13,
55,2,48,42,27,10,
53,5,56,1,59,17,
7,10,28,40,48,32,
56,20,14,5,3,1,
43,40,7,32,55,34,
59,16,3,21,54,20,
10,27,42,48,2,55,
17,59,1,56,5,53,
32,48,40,28,10,7,
1,3,5,14,20,56,
34,55,32,7,40,43,
20,54,21,3,16,59,
44,34,27,2,28,8,
14,21,59,5,54,20,
55,2,48,10,43,42,
59,16,3,20,53,21,
28,42,55,40,27,10,
13,17,54,16,14,4,
40,44,10,55,8,43,
4,14,17,53,20,3,
34,55,32,7,42,44,
17,59,1,56,21,13,
8,28,34,43,10,48,
5,13,20,59,4,53
};
int n7[49][7]=
{
109,65,14,84,88,16,96,
108,34,27,2,28,40,112,
3,20,53,81,110,84,56,
107,0,107,8,119,42,28,
96,20,86,69,59,21,14,
27,34,108,32,28,10,7,
91,65,56,21,13,4,3,
65,99,21,86,68,56,16,
34,119,32,7,42,108,40,
20,54,69,91,5,86,84,
0,0,8,28,34,107,42,
20,54,81,109,80,53,21,
34,119,2,112,42,27,10,
65,99,84,53,17,14,4,
14,21,59,5,54,68,88,
27,32,107,8,119,42,28,
53,69,88,17,99,5,110,
107,8,119,34,0,34,119,
86,81,13,68,99,80,59,
108,2,107,8,119,42,28,
56,84,110,80,54,17,13,
84,86,5,91,5,86,84,
2,7,8,27,8,7,2,
81,91,17,96,17,91,81,
8,28,34,107,34,28,8,
69,109,68,3,68,109,69,
32,112,8,108,8,112,32,
21,53,80,109,80,53,21,
88,68,54,5,59,21,14,
28,42,119,8,107,32,27,
110,5,99,17,88,69,53,
119,34,0,34,119,8,107,
59,80,99,68,13,81,86,
28,42,119,8,107,2,108,
13,17,54,80,110,84,56,
16,56,68,86,21,99,65,
40,108,42,7,32,119,34,
84,86,5,91,69,54,20,
42,107,34,28,8,0,0,
21,53,80,109,81,54,20,
10,27,42,112,2,119,34,
4,14,17,53,84,99,65,
96,16,88,84,14,65,109,
112,40,28,2,27,34,108,
56,84,110,81,53,20,3,
28,42,119,8,107,0,107,
14,21,59,69,86,20,96,
7,10,28,32,108,34,27,
3,4,13,21,56,65,91
};
int n8[64][8]=
{
220,138,7,128,199,170,108,40,
214,81,13,64,237,1,238,68,27,0,27,32,107,168,199,130,237,81,54,16,14,5,3,1,183,138,108,8,112,160,192,128,216,0,216,4,214,21,227,65,107,138,176,2,183,128,119,34,
59,81,224,1,227,85,54,20,138,219,10,192,42,171,130,108,81,219,17,224,65,3,69,238,0,0,32,112,136,172,42,199,81,219,65,56,21,13,4,3,138,219,130,28,168,176,32,192,0,0,4,14,17,53,84,227,138,219,136,7,130,192,162,119,
81,219,80,3,84,213,65,54,
7,10,28,160,172,2,171,170,
13,17,54,16,14,5,3,1,
27,32,107,136,183,10,172,168,
54,65,213,68,59,20,13,5,
108,130,171,34,220,40,176,160,
216,4,214,17,237,80,53,21,
176,136,108,8,112,160,192,128,
224,80,56,5,53,64,213,85,
128,192,160,112,136,172,42,199,
64,224,16,216,84,14,65,237,
32,112,136,172,10,183,136,107,
16,56,68,214,69,59,21,14,
8,28,34,107,162,220,168,112,
4,14,17,53,80,237,17,214,
2,7,8,27,42,112,130,183,
1,3,5,14,17,53,84,227,
199,42,172,136,112,160,192,128,
237,65,14,84,216,16,224,64,
107,136,183,10,172,136,112,32,
14,21,59,69,214,68,56,16,
112,168,220,162,107,34,28,8,
214,17,237,80,53,17,14,4,
183,130,112,42,27,8,7,2,
227,84,53,17,14,5,3,1,
170,171,2,172,160,28,10,7,
1,3,5,14,16,54,17,13,
168,172,10,183,136,107,32,27,
5,13,20,59,68,213,65,54,
160,176,40,220,34,171,130,108,
21,53,80,237,17,214,4,216,
128,192,160,112,8,108,136,176,
85,213,64,53,5,56,80,224,
108,130,171,42,192,10,219,138,
238,69,3,65,224,17,219,81,
199,42,172,136,112,32,0,0,
3,4,13,21,56,65,219,81,
192,32,176,168,28,130,219,138,
227,84,53,17,14,4,0,0,
119,162,192,130,7,136,219,138,
54,65,213,84,3,80,219,81,
40,108,170,199,128,7,138,220,
68,238,1,237,64,13,81,214,
130,199,168,107,32,27,0,27,
1,3,5,14,16,54,81,237,
128,192,160,112,8,108,138,183,
65,227,21,214,4,216,0,216,
34,119,128,183,2,176,138,107,
20,54,85,227,1,224,81,59
};

int ans[80];
int b[10];
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
int sum=0;
for(int i=0; i<n; i++)
scanf("%d",&b[i]);
if(n==4||n==5)
{
init();
for(int i=0; i<n; i++)
{
int r=(i+1)*n-1,l=i*n;
while(r>=l)
{
a[r][var]=b[i]&1;
b[i]>>=1;
r--;
}
}
int ans=Gauss();
printf("%d\n",ans);
continue;
}
if(n==1)
{
printf("%d\n",b[0]);
continue;
}
equ=n*n;
memset(ans,0,sizeof(ans[0])*(equ+4));
if(n==2)
{
for(int j=0; j<n; j++)
if(b[j])
{
for(int i=0; i<equ; i++)
ans[i]=ans[i]^(n2[i][j]&b[j]);
}
}
else if(n==3)
{
for(int j=0; j<n; j++)
if(b[j])
{
for(int i=0; i<equ; i++)
ans[i]=ans[i]^(n3[i][j]&b[j]);
}
}
else if(n==6)
{
for(int j=0; j<n; j++)
if(b[j])
{
for(int i=0; i<equ; i++)
ans[i]=ans[i]^(n6[i][j]&b[j]);
}
}
else if(n==7)
{
for(int j=0; j<n; j++)
if(b[j])
{
for(int i=0; i<equ; i++)
ans[i]=ans[i]^(n7[i][j]&b[j]);
}
}
else if(n==8)
{
for(int j=0; j<n; j++)
if(b[j])
{
for(int i=0; i<equ; i++)
ans[i]=ans[i]^(n8[i][j]&b[j]);
}
}
for(int i=0; i<equ; i++)
{
int cnt=0;
while(ans[i])
{
cnt^=(ans[i]&1);
ans[i]>>=1;
}
sum+=cnt;
}
printf("%d\n",sum);
}
return 0;
}