POJ 2260 Error Correction 解题报告

 

资源来源：http://blog.chinaunix.net/u3/105033/index.html

 

一、问题描述

   

一个布尔矩阵，如果每一行和每一列的元素和都为偶数的话，那么这个矩阵就具有相等属性（parity property）。下面这个4X4的矩阵就具有相等属性。

1 0 1 0

0 0 0 0

1 1 1 1

0 1 0 1

各行的和分别为： 2, 0, 4 和 2. 各列的和分别为： 2, 2, 2 和 2。编写程序判断矩阵是否具有相等属性。如果没有，判断是否可以改变矩阵的一个元素使其具有相等属性。如果没有的话，矩阵被视为是退化的。

Input

矩阵行（列）数n<100，矩阵元素为0或1。

Output

具有相等属性输出"OK"；

可以通过改变一个元素使其具有相等属性的话输出"Change bit (i,j)"；

否则输出"Corrupt"；

Sample Input

4

1 0 1 0

0 0 0 0

1 1 1 1

0 1 0 1

4

1 0 1 0

0 0 1 0

1 1 1 1

0 1 0 1

4

1 0 1 0

0 1 1 0

1 1 1 1

0 1 0 1

0

Sample Output

OK

Change bit (2,3)

Corrupt

 

二、代码实现

#include<iostream>
using namespace std;
int main()
{
    int n,i,j;
    cin>>n;
    short matrix[101][101];
    short sum[2][101];
    short errRow;
    short errCol;
    short numRow,numCol;
    while(n!=0)
    {
        for(i=0;i<2;i++)
        {
            for(j=1;j<=n;j++)
            {
                sum[i][j]=0;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cin>>matrix[i][j];
                sum[0][i]+=matrix[i][j];
                sum[1][j]+=matrix[i][j];
            }
        }
        errCol=0;
        errRow=0;
        numCol=0;
        numRow=0;
        for(i=1;i<=n;i++)
        {
            if(sum[0][i]%2==1)
            {
                numRow++;
                errRow=i;
            }
            if(sum[1][i]%2==1)
            {
                numCol++;
                errCol=i;
            }
        }
        if(numCol==0 && numRow==0)
        {
            cout<<"OK"<<endl;
        }
        else
        {
            if(numCol==1 && numRow==1)
            {
                cout<<"Change bit ("<<errRow<<","<<errCol<<")"<<endl;
            }
            else
                cout<<"Corrupt"<<endl;

        }
        cin>>n;
    }
    return 1;
}