2013年9月18日 星期三

UVA 541 - Error Correction

Problem link

Keyword: bit manipulation

Algorithm:

Use XOR operator(^) to calculate if a row or column is with even ones.
(True if even, and vise versa.)
If all rows and columns are even, then no adjustment is needed.
If there are exactly one row and one column with odd ones, then make adjustment to that row and column.
If it fits none of the above situations, then it's impossible to fix it and you should print out "corrupt."
If you're not familiar with bit manipulation, you may also use an integer to count.

Code:
#include<cstdio>

int main()
{
    int size;

    while( scanf( "%d", &size ) && size )
    {
        bool row[ 100 ] = { false }, col[ 100 ] = { false };
        int field[ 100 ][ 100 ] = { 0 }, R = 0, C = 0, oddR, oddC;
        for( int i = 0; i < size; ++i )
            for( int j = 0; j < size; ++j )
            {
                scanf( "%d", field[ i ]+j );
                row[ i ] ^= field[ i ][ j ];
                col[ j ] ^= field[ i ][ j ];
            }
        for( int i = 0; i < size; ++i )
        {
            R += row[ i ];
            C += col[ i ];
            if( row[ i ] )
                oddR = i+1;
            if( col[ i ] )
                oddC = i+1;
        }
        if( !R && !C )
            puts( "OK" );
        else if( R == 1 && C == 1 )
            printf( "Change bit (%d,%d)\n", oddR, oddC );
        else
            puts( "Corrupt" );
    }

    return 0;
}

沒有留言:

張貼留言