北大 acm 2260 Error Correction 解题报告

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3214 Accepted: 2190

Description

A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here’s a 4 x 4 matrix which has the parity property:
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2.
Your job is to write a program that reads in a matrix and checks if it has the parity property. If not, your program should check if the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt.

Input

The input will contain one or more test cases. The first line of each test case contains one integer n (n<100), representing the size of the matrix. On the next n lines, there will be n integers per line. No other integers than 0 and 1 will occur in the matrix. Input will be terminated by a value of 0 for n.

Output

For each matrix in the input file, print one line. If the matrix already has the parity property, print “OK”. If the parity property can be established by changing one bit, print “Change bit (i,j)” where i is the row and j the column of the bit to be changed. Otherwise, print “Corrupt”.

Sample Input

41 0 1 00 0 0 01 1 1 10 1 0 141 0 1 00 0 1 01 1 1 10 1 0 141 0 1 00 1 1 01 1 1 10 1 0 10

Sample Output

OKChange bit (2,3)Corrupt

题意：二维矩阵每行或者每列各个数的和是否偶数，若果是输出ok，如果不是问更改一次能否让矩阵满足全部为偶数，如果可以输出该数下标，如果不行则输出Corrupt

代码如下

#include <iostream>

using namespace std;

int main()
{
  int n,a[201][201]={0},line[201]={0},coulum[201]={0};
  int i,j,k,lin, cou,haveeven;

  while(cin>>n&&n)
  {
    k=haveeven=0;

    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
        cin>>a[i][j];    
        if(a[i][j]==1)
        {
          line[i]++;
          coulum[j]++;
        }   //计算每行列的总数
      }

     for(i=1;i<=n;i++)
     {
       if(line[i]%2!=0)
       {
          haveeven=1; //如果发现奇数则haveeven赋值为1

          for(j=1;j<=n;j++)
            if(coulum[j]%2!=0)
            {
              if(a[i][j]==1)
              {
                line[i]--;
                coulum[j]--;
                a[i][j]=0;
              }
              else
              {
                a[i][j]=1;
                line[i]++;
                coulum[j]++;
              }

            haveeven=0;//若找到与之配对是奇数列，则haveeven赋值为0
            k++; //k表示共找到几处是奇数的行或列
            lin=i;
            cou=j;
          }
      }

      if(haveeven==1||k>1)
        break;//如果奇数未配对，或者找到大于1的奇数行或列结束循环

      if(coulum[i]%2!=0)
      {
        haveeven=1;
        for(j=1;j<=n;j++)
          if(line[j]%2!=0)
          {
            if(a[j][i]==1)
            {
             line[j]--;
             coulum[i]--;
             a[j][i]=0;
            }
            else
            {
             a[j][i]=1;
             line[j]++;
             coulum[i]++;
            }

          haveeven=0;
          k++;
          lin=j;
          cou=i;
        }
      }


      if(haveeven==1||k>1)
        break;
    }

    if(k==0&&haveeven==0)
      cout<<"OK"<<endl;

    if(k==1&&haveeven==0)
      cout<<"Change bit ("<<lin<<","<<cou<<")"<<endl;

    if(k>1||haveeven==1)
      cout<<"Corrupt"<<endl;

    for(i=1;i<=n;i++)
      line[i]=coulum[i]=0;
  }

  return 0;
}