原始题目

Error Correction

• Time Limit: 1000MS
  
• Memory Limit: 65536K
• Total Submissions: 6820
  
• Accepted: 4286

Problem 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

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

Source

Ulm Local 1998

题目大意

给定一个n*n的由0/1构成的boolean矩阵，判断是否各行各列和均为偶数。

若是输出OK，若不是，可否更改其中一点的位置使行列均为偶数。输出这个点，若不可以，输出Corrupt

解题思路

改一个点即可的充要条件为行和列之中存在且仅有一行与一列的各自的和为奇数。

或者利用邻接矩阵的知识转化为有向图+深度优先搜索？？学姐讲的图论知识，还没有深入学习。