Poj Solution 1812

http://poj.org/problem?id=1812

#include <stdio.h>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

char op[10];
int opn, ans;

void search( int h, const int *str, int len ) {
    int i, j, k;

    if( h >= ans )
        return;    

    if( len == 0 ) {
        ans = h;
        return;
    }

    if( h == opn )
        return;

    int w[20];
    
    for( i=0; i<len; i++ ) {
        if( (str[i]&255) == op[h] ) {
            memcpy( w, str, len*sizeof(int) );
            w[i] += (1<<8);
            if( (w[i]>>8) >= 3 ) {
                for( j=i-1, k=i+1; j>=0 && k<len && (w[j]&255)==(w[k]&255); j--, k++ ) {
                    w[j] += (w[k]>>8<<8);
                    if( (w[j]>>8) < 3 ) {
                        k++;
                        break;
                    }
                }
                while( k<len )
                    w[++j] = w[k++];
                search( h+1, w, j+1 );
            }
            else
                search( h+1, w, len );
        }
    }

}

int main( ) {
    int t, len, i;
    char w[21];
    int str[20], l;

    scanf( "%d", &t );

    while( t-- ) {
        scanf( "%d%d", &len, &opn );
        scanf( "%s", w );

        for( l=0, i=0; i<len; i++ ) {
            if( !i || w[i] != w[i-1] )
                str[l++] = (1<<8) | w[i];
            else
                str[l-1] += (1<<8);
        }
        ans = 6;
        
        scanf( "%s", op );
        sort( op, op+opn );

        do {
            search( 0, str, l );
        } while( next_permutation( op, op+opn ) );

        if( ans == 6 )
            printf( "losen" );
        else
            printf( "%dn", ans );
    }
    return 0;
}




											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *