プログラマ専用SNS ミクプラ

コード:

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

//２次元配列
const int W = 4;
const int H = 4;
unsigned int Map[H][W];

//作るべき部屋のサイズ範囲
const unsigned int MinRoomSize = 2;
const unsigned int MaxRoomSize = 4;

//作業用
const int MAP_SIZE = W*H;
unsigned int RoomSize[ MAP_SIZE ];  //RoomSize[部屋番号]で部屋のサイズ．ただしもはや存在しない部屋の値は0


//初期状態生成
void Initialize()
{
    unsigned int RoomNumber = 0;
    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            Map[y][x] = RoomNumber;
            ++RoomNumber;
        }
    }

    for( int i=0; i<MAP_SIZE; i++ )
    {   RoomSize[i] = 1;    }
}

//現状を出力
void PrintMap()
{
    for( int y=0; y<H; y++ )
    {
        printf( "%2u", Map[y][0] );
        for( int x=1; x<W; x++ )
        {   printf( ",%2u", Map[y][x] );    }
        printf( "\n" );
    }
    printf( "\n" );
}

//目標達成しているかどうか
bool Complete()
{
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        unsigned int s = RoomSize[i];
        if( s==0 )continue;
        if( s<MinRoomSize || MaxRoomSize<s )return false;
    }
    return true;
}

//サイズ最小な部屋の番号をひとつ返す
unsigned int GetSmallestRoom()
{
    unsigned int MinSize = std::numeric_limits<unsigned int>::max();
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i]>0 && RoomSize[i]<MinSize )
        {   MinSize = RoomSize[i];  }
    }

    std::vector< unsigned int > Tmp;
    Tmp.reserve( MAP_SIZE );
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i] == MinSize )
        {   Tmp.push_back( i ); }
    }

    std::random_shuffle( Tmp.begin(), Tmp.end() );
    return Tmp.front();
}

//２つの部屋を合併．
void IntegrateRoom( unsigned int RoomNum1, unsigned int RoomNum2 )
{
    //RoomNum1番側に取り込む
    RoomSize[ RoomNum1 ] += RoomSize[ RoomNum2 ];
    RoomSize[ RoomNum2 ] = 0;

    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] == RoomNum2 )
            {   Map[y][x] = RoomNum1;   }
        }
    }
}

//RoomNum番の部屋に隣接する部屋を調査
void SearchNeighbor(
    unsigned int RoomNum,
    std::vector<unsigned int> &rDstSafeIntegratable,    //合併しても最大サイズを超えない部屋番号を格納
    std::vector<unsigned int> &rDstSizeOver //合併すると最大サイズを超える部屋番号を格納
    )
{
    const int dx[4] = { 0, -1, 1, 0 };
    const int dy[4] = { -1, 0, 0, 1 };

    rDstSafeIntegratable.clear();
    rDstSizeOver.clear();

    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] != RoomNum )continue;

            for( int dir=0; dir<4; dir++ )
            {
                int xx = x + dx[dir];
                int yy = y + dy[dir];
                if( xx<0 || xx>=W || yy<0 || yy>=H )continue;
                unsigned int rn = Map[yy][xx];
                if( rn==RoomNum )continue;

                unsigned int IntegratedSize = RoomSize[RoomNum] + RoomSize[rn];
                if( IntegratedSize < MaxRoomSize )
                {   rDstSafeIntegratable.push_back( rn );   }
                else
                {   rDstSizeOver.push_back( rn );   }
            }
        }
    }

    std::sort( rDstSafeIntegratable.begin(), rDstSafeIntegratable.end() );
    rDstSafeIntegratable.erase( std::unique( rDstSafeIntegratable.begin(), rDstSafeIntegratable.end() ), rDstSafeIntegratable.end() );

    std::sort( rDstSizeOver.begin(), rDstSizeOver.end() );
    rDstSizeOver.erase( std::unique( rDstSizeOver.begin(), rDstSizeOver.end() ), rDstSizeOver.end() );
}

//サイズオーバーな部屋を探す
bool FindSizeOverRoom( unsigned int &rDstRoomNum )
{
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i]>MaxRoomSize )
        {
            rDstRoomNum = i;
            return true;
        }
    }
    return false;
}

//RoomNum番の部屋をばらばらに解体する
void DestructRoom( unsigned int RoomNum )
{
    RoomSize[ RoomNum ] = 0;

    unsigned int NewRoomNum = 0;
    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] != RoomNum )continue;

            while( RoomSize[NewRoomNum]>0 )
            {   ++NewRoomNum;   }

            Map[y][x] = NewRoomNum;
            RoomSize[NewRoomNum] = 1;
        }
    }
}

//main
int main()
{
    //乱数系列初期化
    //引数を変えれば結果が変わる
    std::srand( 10 );   //※std::random_shuffle()に影響するのはコレでいいのだろうか？

    //初期状態準備
    Initialize();
    printf( "初期状態\n" );
    PrintMap();

    //がんぱる
    std::vector< unsigned int > SafeIntegratableTgts;
    std::vector< unsigned int > SizeOverTgts;

    SafeIntegratableTgts.reserve( MAP_SIZE );
    SizeOverTgts.reserve( MAP_SIZE );

    unsigned int turn = 0;
    while( true )
    {
        ++turn;

        if( Complete() )
        {
            printf( "できた\n" );
            break;
        }
        if( turn > 100 )    //※どうしてもできないときの無限ループ防止
        {
            printf( "もうあきらめる\n" );
            break;
        }

        printf( "Turn %u\n", turn );

        unsigned int RoomNum1;
        if( FindSizeOverRoom( RoomNum1 ) )
        {
            printf( "Destruct Room%u(%u)\n", RoomNum1, RoomSize[RoomNum1] );
            DestructRoom( RoomNum1 );
        }
        else
        {
            RoomNum1 = GetSmallestRoom();
            SearchNeighbor( RoomNum1, SafeIntegratableTgts, SizeOverTgts );

            std::vector< unsigned int > &rTgts = ( !SafeIntegratableTgts.empty()  ?  SafeIntegratableTgts  :  SizeOverTgts );
            std::random_shuffle( rTgts.begin(), rTgts.end() );
            unsigned int RoomNum2 = rTgts.front();
        
            printf( "Room%u(%u) + Room%u(%u)\n", RoomNum1, RoomSize[RoomNum1], RoomNum2, RoomSize[RoomNum2] );
            if( SafeIntegratableTgts.empty() ){ printf( "(Size Over)\n" );  }

            IntegrateRoom( RoomNum1, RoomNum2 );
        }

        PrintMap();
    }

    //
    printf( "\n==Enter to quit==\n" );
    getchar();  //※Enter押すまで待つ用
    return 0;
}