# 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.