PKU 1027 The Same Game

The Same Game

懐かしい。
C++だとTLE、G++で900MS。通ったから良しとしよう……。

#include <iostream>

using namespace std;

const int W = 15;
const int H = 10;

void cluster( char b[W][H], int c[W][H] );
void fall( char b[W][H] );

int main()
{
    int n;
    cin >> n;

    for ( int i=1; i<=n; i++ )
    {
        char b[W][H];

        for ( int y=H-1; y>=0; y-- )
        for ( int x=0; x<W; x++ )
            cin >> b[x][y];

        cout << "Game " << i << ":" << endl;
        cout << endl;

        int remain = W * H;
        int score = 0;

        for ( int j=1; remain>0; j++ )
        {
            int c[W][H];
            cluster( b, c );

            int num[W*H] = { 0 };   //  各クラスタの玉数
            for ( int x=0; x<W; x++ )
            for ( int y=0; y<H; y++ )
                if ( c[x][y] >= 0 )
                    num[c[x][y]]++;

            int m = 0;              //  最も大きいクラスタの玉数
            int mx, my;             //  もっとも大きいクラスタの左下の玉

            for ( int x=0; x<W; x++ )
            for ( int y=0; y<H; y++ )
                if ( c[x][y] >= 0  &&  num[c[x][y]] > m )
                    m = num[c[x][y]],
                    mx = x,  my = y;

            if ( m <= 1 )
                break;

            //  玉を消す
            char color = b[mx][my];

            for ( int x=0; x<W; x++ )
            for ( int y=0; y<H; y++ )
                if ( c[x][y] == c[mx][my] )
                    b[x][y] = ' ';
                    
            remain -= m;

            int point = (m-2)*(m-2);
            score += point;

            fall( b );

            //  表示
            cout << "Move " << j
                 << " at (" << my+1 << "," << mx+1 << "): "
                 << "removed " << m << " balls"
                 << " of color " << color << ", "
                 << "got " << point << " points." << endl;
        }

        if ( remain == 0 )
            score += 1000;

        cout << "Final score: " << score << ", "
             << "with " << remain << " balls remaining." << endl;

        if ( i < n )
            cout << endl;
    }

    return 0;
}

//  bをクラスタに分ける
void cluster( char b[W][H], int c[W][H] )
{
    for ( int x=0; x<W; x++ )
    for ( int y=0; y<H; y++ )
        c[x][y] = -1;

    bool f[W][H] = { { false } };

    for ( int i=0; ; i++ )
    {
        //  クラスタ分けされていない玉を探す
        for ( int x=0; x<W; x++ )
        for ( int y=0; y<H; y++ )
            if ( b[x][y] != ' '  &&  c[x][y] == -1 )
            {
                c[x][y] = i;
                f[x][y] = true;
                goto found;
            }
        break;

        found:;
        //  隣接している玉をクラスタに分ける
        bool update;
        do
        {
            update = false;

            for ( int x=0; x<W; x++ )
            for ( int y=0; y<H; y++ )
            if ( f[x][y] )
            for ( int d=0; d<4; d++ )
            {
                int tx = x;
                int ty = y;

                switch ( d )
                {
                case 0:  tx++;  break;
                case 1:  ty++;  break;
                case 2:  tx--;  break;
                case 3:  ty--;  break;
                }

                if ( 0 <= tx  &&  tx < W  &&  0 <= ty  &&  ty < H  &&
                     b[tx][ty] == b[x][y]  &&  c[tx][ty] == -1 )
                {
                    c[tx][ty] = i;
                    f[tx][ty] = true;
                    update = true;
                }

                f[x][y] = false;
            }

        } while ( update );
    }
}

//  玉を詰める
void fall( char b[W][H] )
{
    //  縦方向
    for ( int x=0; x<W; x++ )
    for ( int y=0; y<H-1; y++ )
    if ( b[x][y] == ' ' )
    {
        int t;
        for ( t=y+1; t<H-1 && b[x][t]==' '; t++ )
            ;
        b[x][y] = b[x][t];
        b[x][t] = ' ';

        if ( t == H-1 )
            break;
    }
    
    //  横方向
    for ( int x=0; x<W-1; x++ )
    if ( b[x][0] == ' ' )
    {
        int t;
        for ( t=x+1; t<W-1 && b[t][0]==' '; t++ )
            ;
        for ( int y=0; y<H; y++ )
            b[x][y] = b[t][y],
            b[t][y] = ' ';

        if ( t == W-1 )
            break;
    }
}