View Code of Problem 3376

#include<stdio.h>
#include<string.h>

#define NN 155 

char str[NN], cha[NN];
int mark[NN][NN], num[NN];

int dfs(int l, int r){
    int i, t;
    if(l == r){
        if(num[l] > 1)
            return 1;
        else
            return 0;
    }
    if(mark[l][r] >= 0)
        return mark[l][r];

    char ch = cha[l];
    for(int i = l + 1; i <= r; i++){
        if(cha[i] == ch)
            if(mark[l + 1][i - 1] = dfs(l + 1, i - 1)){
                t = mark[i][r];
                mark[i][r] = -1;
                num[i] += num[l];
                mark[i][r] = dfs(i, r);
                num[i] -= num[l];
                if(mark[i][r] == 1){
                    mark[i][r] = t;
                    return 1;
                }
                mark[i][r] = t;
            }
    }
    if(num[l] > 1 && (mark[l + 1][r] = dfs(l + 1, r)))
        return 1;
    return 0;
}

int main(){
    while(scanf("%s", str) != EOF){
        if(!strlen(str)){
            printf("solvable\n");
            continue;
        }

        int time = 1, index = 0;
        for(int i = 0; str[i]; i++){
            if(str[i + 1] != str[i]){
                cha[index] = str[i];
                num[index] = time;
                time = 1;
                index++;
            }
            else
                time++;
        }    
        memset(mark, -1, sizeof(mark));
        if(dfs(0, index - 1))
            printf("solvable\n");
        else
            printf("unsolvable\n");
    }
    return 0;
}