PKU 1021 2D-Nim

2D-Nim

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct XY
{
    int x, y;

    XY() {}
    XY( int x_, int y_ ) : x(x_), y(y_) {}
    bool operator<( const XY &a ) const
        { return x<a.x  ||  x==a.x && y<a.y; }
    bool operator==( const XY &a ) const
        { return x==a.x && y==a.y; }
};

vector<vector<XY> > split( vector<XY> p, int W, int H );
bool equal( vector<XY> *b1, vector<XY> *b2 );
void normalize( vector<XY> *c );
void rotate( vector<XY> *c );
void reflect( vector<XY> *c );

int main()
{
    int t;  cin >> t;
    while ( t-- > 0 )
    {
        //  読み込み
        int W, H, n;
        cin >> W >> H >> n;

        vector<vector<XY> > board[2];

        for ( int i=0; i<2; i++ )
        {
            vector<XY> p(n);
            for ( int j=0; j<n; j++ )
                cin >> p[j].x >> p[j].y;
             board[i] = split( p, W, H );
        }

        //  board[0] の各クラスタと同じクラスタを board[1] から消す
        bool correct = true;

        for ( int i=0; i<(int)board[0].size(); i++ )
        {
            int j;
            for ( j=0; j<(int)board[1].size(); j++ )
                if ( equal( &board[0][i], &board[1][j] ) )
                    break;

            if ( j >= (int)board[1].size() )
            {
                correct = false;
                break;
            }
            
            board[1].erase( board[1].begin() + j );
        }

        if ( board[1].size() != 0 )
            correct = false;
        
        cout << ( correct ? "YES" : "NO" ) << endl;
    }

    return 0;
}

//  ピースをクラスタに分割
vector<vector<XY> > split( vector<XY> p, int W, int H )
{
    //  -2：空　-1：未分類　0-：分類済み
    vector<vector<int> > board( W+2, vector<int>(H+2,-2) );
    
    for ( int i=0; i<(int)p.size(); i++ )
        board[p[i].x+1][p[i].y+1] = -1;

    vector<vector<XY> > cluster;

    for ( int n=0; ; n++ )
    {
        //  未分類のピースを探す
        int x, y;
        for ( x=1; x<=W; x++ )
        for ( y=1; y<=H; y++ )
            if ( board[x][y] == -1 )
                goto found;
        found:;

        if ( x > W )
            break;

        //  未分類のピースに番号を振る
        board[x][y] = n;

        cluster.push_back( vector<XY>() );
        cluster[n].push_back( XY(x,y) );

        //  未分類かつ分類済みのピースに隣接しているピースを加える
        bool update;
        do
        {
            update = false;         

            for ( int x=1; x<=W; x++ )
            for ( int y=1; y<=H; y++ )
            if ( board[x][y] == -1 )
            {
                if ( board[x-1][y] == n  ||
                     board[x+1][y] == n  ||
                     board[x][y-1] == n  ||
                     board[x][y+1] == n )
                {
                    board[x][y] = n;
                    cluster[n].push_back( XY(x,y) );
                    update = true;
                }
            }
        } while ( update );
    }

    return cluster;
}

//  b1 と b2 が等しいかどうか調べる
bool equal( vector<XY> *b1, vector<XY> *b2 )
{
    for ( int i=0; i<2; i++ )
    {
        for ( int j=0; j<4; j++ )
        {
            normalize( b1 );
            normalize( b2 );

            if ( *b1 == *b2 )
                return true;

            rotate( b2 );
        }
        reflect( b2 );
    }

    return false;
}

//  正規化
//  x=0, y=0 のピースが少なくとも１枚ずつ含まれるように移動し、
//  ピースを位置でソートする
void normalize( vector<XY> *c )
{
    int mx = INT_MAX;
    int my = INT_MAX;

    for ( int i=0; i<(int)c->size(); i++ )
        mx = min( mx, (*c)[i].x ),
        my = min( my, (*c)[i].y );

    for ( int i=0; i<(int)c->size(); i++ )
        (*c)[i].x -= mx,
        (*c)[i].y -= my;

    sort( c->begin(), c->end() );
}

//  ピースを90度回転
void rotate( vector<XY> *c )
{
    for ( int i=0; i<(int)c->size(); i++ )
    {
        int t = (*c)[i].x;
        (*c)[i].x = (*c)[i].y;
        (*c)[i].y = -t;
    }
}

//  ピースを反転
void reflect( vector<XY> *c )
{
    for ( int i=0; i<(int)c->size(); i++ )
        (*c)[i].x = -(*c)[i].x;
}