Matrix

Description

给你一个N*M 的矩阵，矩阵里面的元素要么是正数，要么是负数，它们的绝对值不大
于10000。现在你可以对矩阵进行两种操作：
1、将某一列的元素全部取反。
2、将某一行的元素全部取反。
你可以执行任意次操作。
Task：通过以上两种操作如果可以将整个矩阵的元素全变为正数的话，则输出最少的操
作次数，否则输出“impossible”（不包括双引号）。

Input

输入文件的第一行有两个整数n 和m(1≤n,m≤1000)，表示矩阵的大小。
接下来有N 行，每行M 个数，每个数之间有一个空格。

Output

通过以上两种操作如果可以将整个矩阵的元素全变为正数的话，则输出最少的操作次
数，否则输出“impossible”（不包括双引号）。

Sample Input

2 4
3 7 -6 1
-2 -6 8 -4

Sample Output

2

Data Constraint

Hint

数据约定：
对于40%的数据,1≤N,M≤10
对于100%的数据，2≤N，M≤1000
.
.
.
.
.
.

分析

对于每一行，统计负数的个数，若负数较多就把每个负数所在列取反，否则把这行取反，如果有一列取反了2次就是impossible，最后ans=min(ans,n+m-ans)，最多操作n+m次。
.
.
.
.
.
.

程序：

#include<iostream>
#include<fstream>
using namespace std;
int n,m;
int a[2000],b[2000],c[1001][1001],b1[1001],a1[1001];
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            b[j]=0;
            b1[j]=1;
            cin>>c[i][j];
        }
        a[i]=0;
        a1[i]=1;
    }
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        int zs=0,fs=0;
        for (int j=1;j<=m;j++)
        if (c[i][j]*a1[i]*b1[j]<0) fs++; else zs++;
        if (fs<zs) 
        {
            for (int j=1;j<=m;j++)
            if (c[i][j]*a1[i]*b1[j]<0)
            {
                b[j]++;
                if (b[j]==2)
                {
                    cout<<"impossible";
                    return 0;
                }
                b1[j]*=-1;
                ans++;
            }
        }
        if (fs>=zs)
        {
            a[i]++;
            if (a[i]==2)
            {
                cout<<"impossible";
                return 0;
            }
            a1[i]*=-1;
            ans++;
            for (int j=1;j<=m;j++)
            if (c[i][j]*a1[i]*b1[j]<0)
            {
                b[j]++;
                if (b[j]==2)
                {
                    cout<<"impossible";
                    return 0;
                }
                b1[j]*=-1;
                ans++;
            }
        }
    }
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    if (c[i][j]*a1[i]*b1[j]<0) 
    {
        cout<<"impossible";
        return 0;
    }
    if (ans>(n+m)/2) cout<<n+m-ans;else cout<<ans;
    return 0;
    fclose(stdin);
    fclose(stdout);
}