PKU 1020 Anniversary Cake

Anniversary Cake

バックトラック。余りが出ないようにという条件があるので、各深さでは最初に見つけたケーキの残りを切り取ればよい。

#include <iostream>
#include <numeric>

using namespace std;

int     s;                  //  ケーキサイズ
bool    cake[99][99];       //  ケーキ
int     piece[11];          //  添字の大きさのピースの個数

bool    BT();

int main()
{
    int t;  cin >> t;
    while ( t-- > 0 )
    {
        //  入力
        int n;
        cin >> s >> n;

        for ( int i=1; i<=10; i++ )
            piece[i] = 0;

        for ( int i=0; i<n; i++ )
        {
            int a;  cin >> a;
            piece[a]++;
        }

        //  探索
        for ( int x=0; x<s; x++ )
        for ( int y=0; y<s; y++ )
            cake[x][y] = true;

        bool success = true;

        int sum = 0;
        for ( int i=1; i<=10; i++ )
            sum += piece[i] * i*i;
        if ( sum != s*s )
            success = false;

        if ( success )
            success = BT();

        cout << ( success ? "KHOOOOB!" : "HUTUTU!" ) << endl;
    }

    return 0;
}

bool BT()
{
    //  全て切り取れたら終了
    if ( accumulate( piece+1, piece+11, 0 ) == 0 )
        return true;

    //  ケーキが残っている場所を探す
    int x, y;
    for ( x=0; x<s; x++ )
    for ( y=0; y<s; y++ )
        if ( cake[x][y] )
            goto found;
    found:;

    //  各サイズのピースを切り取って再帰
    for ( int i=10; i>0; i-- )
    if ( piece[i] > 0  &&
         x + i <= s  &&  y + i <= s )
    {
        bool ok = true;
        for ( int xx=0; xx<i && ok; xx++ )
        for ( int yy=0; yy<i && ok; yy++ )
            if ( ! cake[x+xx][y+yy] )
                ok = false;

        if ( ! ok )
            continue;

        piece[i]--;
        for ( int xx=0; xx<i; xx++ )
        for ( int yy=0; yy<i; yy++ )
            cake[x+xx][y+yy] = false;
        
        bool f = BT();

        piece[i]++;
        for ( int xx=0; xx<i; xx++ )
        for ( int yy=0; yy<i; yy++ )
            cake[x+xx][y+yy] = true;

        if ( f )
            return true;
    }

    return false;
}

コメントと改行を削って、GCC 444B。2009/12/13 現在最短。

s,          //  ケーキのサイズ
c[64][64],  //  [0][0]：ピース数
            //  [1-10][0]：添字の大きさのピース数
            //  [1-][1-]：ケーキ
f,j;

B(x,y,i)
{
    //  ケーキが残っている場所を探す
    for(i=0;i<s*s&!c[x=i%s][y=i/s+1];i++);

    //  残りが無ければ終了
    if(i>=s*s)
        return 1;

    for(i=10;i;++*c[i--])
    {
        //  サイズ i の大きさのピースが切り取れるか調べる
        for(j=i*i;~--j&&c[x+j%i][y+j/i];);
        
        //  サイズ i のピースが残っていれば切り取る
        if(~--*c[i]&&!~j)
        {
            for(j=i*i;~--j;)
                c[x+j%i][y+j/i]=0;

            //  再帰
            f=B();

            for(j=i*i;~--j;)
                c[x+j%i][y+j/i]=1;

            //  残りのピースも切り取れればOK
            if(f)
                return 1;
        }
    }
    return 0;
}

main(t)
{
    for(scanf("%d",&t);t--;puts(f==s*s&&B()?"KHOOOOB!":"HUTUTU!"))
    {
        //  初期化
        memset(c,0,16384);f=0;

        //  読み込み・ピースの合計サイズを計算
        for(scanf("%d%d",&s,*c);~--**c;f+=j*j)
            scanf("%d",&j),
            ++*c[j];

        //  ケーキの初期化
        for(j=s*s;~--j;)
            c[j%s][j/s+1]=1;
    }
}