ACM-ICPC 2010 国内予選問題 Problem D ぐらぐら

Problem D ぐらぐら

問題文の通りに計算するだけ。だが、面倒くさい。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    while ( true )
    {
        //  入力
        int w, h;
        cin >> w >> h;
        if ( w == 0  &&  h == 0 )
            break;

        vector<string> elev( h );
        for ( int i=0; i<h; i++ )
            cin >> elev[i];

        //  ピースを探す
        int num = 0;                //  ピースの個数
        vector<vector<int> > bx;    //  ブロックのx座標
        vector<vector<int> > by;    //  ブロックのy座標

        while ( true )
        {
            //  まだピースに割り当てられていないブロックを探す
            char t = '.';
            for ( int y=0; y<h && t=='.'; y++ )
            for ( int x=0; x<w && t=='.'; x++ )
                if ( elev[y][x] != '.' )
                    t = elev[y][x],
                    elev[y][x] = '*';
            if ( t == '.' )
                break;

            //  隣接しているブロックを'*'に置換
            bool up;
            do
            {
                up = false;
                for ( int y=0; y<h; y++ )
                for ( int x=0; x<w; x++ )
                if ( elev[y][x] == '*' )
                {
                    if ( 0<x   && elev[y][x-1]==t )  elev[y][x-1]='*', up=true;
                    if ( 0<y   && elev[y-1][x]==t )  elev[y-1][x]='*', up=true;
                    if ( x<w-1 && elev[y][x+1]==t )  elev[y][x+1]='*', up=true;
                    if ( y<h-1 && elev[y+1][x]==t )  elev[y+1][x]='*', up=true;
                }
            }
            while ( up );

            //  '*'の座標をピースに割り当てて、'.'に置換
            bx.push_back( vector<int>() );
            by.push_back( vector<int>() );
            
            for ( int y=0; y<h; y++ )
            for ( int x=0; x<w; x++ )
            if ( elev[y][x] == '*' )
            {
                bx[num].push_back( x );
                by[num].push_back( y );
                elev[y][x] = '.';
            }

            num++;
        }

        //  支えられている最左・最右のブロックと支えているピースを計算
        vector<int>         xL( num, w );       //  他ピースに接している最左のブロック
        vector<int>         xR( num, 0 );       //  他ピースに接している最右のブロック
        vector<int>         parent( num, -1 );  //  このピースを支えているピース（-1：地面）
        vector<vector<int> >child( num );       //  このピースが支えているピース

        for ( int p=0; p<num; p++ )
        {
            for ( int b=0; b<4; b++ )
            {
                int s = -1;
                for ( int p2=0; p2<num; p2++ )
                for ( int b2=0; b2<4; b2++ )
                    if ( p2 != p  &&
                         bx[p][b]   == bx[p2][b2]  &&
                         by[p][b]+1 == by[p2][b2] )
                        s = p2;

                if ( s != -1  ||
                     by[p][b] == h - 1 )
                {
                    xL[p] = min( xL[p], bx[p][b] );
                    xR[p] = max( xR[p], bx[p][b] );
                    parent[p] = s;
                }
            }

            if ( parent[p] != -1 )
                child[parent[p]].push_back( p );
        }

        //  重心を計算
        vector<int>     Mn( num, -1 );  //  このピースと支えているピースのブロックの個数（-1：未計算）
        vector<int>     Mx( num, 0  );  //  このピースと支えているピースのブロックのx座標の合計

        bool end = false;

        while ( ! end )
        {
            for ( int p=0; p<num; p++ )
            {
                //  支えているピースが計算済みのピースから求めていく
                bool f = true;
                for ( int c=0; c<(int)child[p].size(); c++ )
                    if ( Mn[child[p][c]] == -1 )
                        f = false;

                if ( f  &&  Mn[p] == -1 )
                {
                    Mn[p] = 0;
                    Mx[p] = 0;

                    for ( int c=0; c<(int)child[p].size(); c++ )
                        Mn[p] += Mn[child[p][c]],
                        Mx[p] += Mx[child[p][c]];

                    for ( int b=0; b<4; b++ )
                        Mn[p]++,
                        Mx[p] += bx[p][b];

                    //  地面に接しているピースの重心が求まれば終了
                    if ( parent[p] == -1 )
                        end = true;
                }
            }
        }

        //  安定性判定
        bool stable = true;

        for ( int p=0; p<num; p++ )
        {
            //  Mx[p]/Mn[p] <= xL[p] - 1/2  ||
            //  Mx[p]/Mn[p] >= xR[p] + 1/2
            if ( Mx[p]*2 <= xL[p]*Mn[p]*2 - Mn[p]  ||
                 Mx[p]*2 >= xR[p]*Mn[p]*2 + Mn[p] )
                stable = false;
        }

        if ( stable )
            cout << "STABLE" << endl;
        else
            cout << "UNSTABLE" << endl;
    }
}