Eva

Time Limit: 1 Sec  Memory Limit: 128 MB
Description

有一个n行n列的棋盘，每个格子上都有一个硬币，且n为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子(x,y)，然后将第x行和第y列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。

Input

第一行包含一个正整数n。

接下来n行，每行包含一个长度为n的01字符串，表示棋盘上硬币的状态。

Output 

仅包含一行，为最少需要的操作数。

Sample Input

4
0101
1000
0010
0101

Sample Output

2

HINT

【样例说明】

对(2,3)和(3,1)进行操作，最后全变成1。

【数据规模】

对于100%的数据，n ≤ 1,000。

 

/**************************************************************

    Problem: 3517

    User: ictsing

    Language: C++

    Result: Accepted

    Time:36 ms

    Memory:5244 kb

****************************************************************/

 

//3517: 翻硬币

/*

翻成白的最小值+翻成黑的最小值==n

我我我，，，我看不懂网上的题解

反正我觉得吧，一个位置只有翻一次，或者不翻的可能，

然后啊，这个地方翻，不翻是取决于当前行的抑或，当前列的抑或，以及他本身的。

所以。。。。。。

*/

#include <iostream>  

#include <cstdio>  

using namespace std;  

const int mt = 1000+5;

int a[mt][mt],h[mt],l[mt];  

char ch[mt];  

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{  

    int n=read();

    for(int i=1;i<=n;i++)

     {  

        scanf("%s",ch+1);  

        for(int j=1;j<=n;j++)

        {  

            a[i][j]=ch[j]-'0';  

            h[i]^=a[i][j],l[j]^=a[i][j];  

        }  

    }  

    int ans=0;  

    for(int i=1;i<=n;i++)  

        for(int j=1;j<=n;j++) 

            ans+=h[i]^l[j]^a[i][j];  

    printf("%d\n",min(ans,n*n-ans));  

    return 0;  

}