bzoj 3517: 翻硬币

3517: 翻硬币

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

有一个nn列的棋盘,每个格子上都有一个硬币,且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。

Source

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1010
int ans,n;
bool a[N][N],sum1[N],sum2[N];
char s[N];
int main()
{
scanf("%d\n",&n);
for(int i=;i<n;i++)
{
gets(s);
for(int j=;j<n;j++)
{
a[i][j]=s[j]-'';
sum1[i]^=a[i][j];
sum2[j]^=a[i][j];
}
}
for(int i=;i<n;i++) for(int j=;j<n;j++) ans+=sum1[i]^sum2[j]^a[i][j];
printf("%d\n",min(ans,n*n-ans));
}
上一篇:jsp 表单回显


下一篇:sudo -u hdfs hdfs balancer出现异常 No lease on /system/balancer.id