题解 | 24点运算

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


#undef DEBUG
#if defined(DEBUG)
#define debug(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#define debug(fmt, ...)
#endif

int dfs(int *num, int *flag, int result, char *com, int *order) ;

int main() {
    char str[24];
    gets(str);
    debug("%s\n",str);
    
    int num[4];
    int i,j;
    for(i = 0; i < strlen(str); i++) {
        switch(str[i]) {
            case 'j':   printf("ERROR\n");
                        return 0;
                        break;
            case 'A' :  num[j++] = 1;  break;
            case 'J' :  num[j++] = 11; break;
            case 'Q' :  num[j++] = 12; break;
            case 'K' :  num[j++] = 13; break;
            case '1' :  if(str[i+1] && str[i+1] == '0')
                        num[j++] = 10; i++; break;
            case ' ' : continue; break;
            default:    num[j++] = str[i] - '0';
                        break; 
        }
    }
    for(j = 0; j < 4; j++)
        debug("data[%d] = %d\n",j , num[j]);
    int flag[4] = {0};
    int order[4];
    char com[3];

    for(i = 0; i < 4; i++) {
        flag[i] = 1;
        order[0] = num[i];
        if(dfs(num,flag,num[i],com,order)) {
            return 0;
        }
        flag[i] = 0;
    }
    printf("NONE\n");
    return 0;
}

inline int checkFlag(int *flag)
{
    return (flag[0] + flag[1]+ flag[2] + flag[3]);
}

int dfs(int *num, int *flag, int result, char *com, int *order) 
{
    int i;
    int idx = checkFlag(flag);
    debug("idx = %d\n",idx);
    if(idx == 4 && result == 24){
        for(i = 0; i < 4; i++) {
            switch(order[i]) {
                case 1:  printf("A"); break;
                case 11: printf("J"); break;
                case 12: printf("Q"); break;
                case 13: printf("K"); break;
                default: printf("%d",order[i]); break;
            }
            if(i < 3) 
                printf("%c",com[i]);
        }
        return 1;
    } else if(idx == 4 && result != 4) {
        return 0;
    }

    for(i = 0; i < 4; i++) {
        if(flag[i] != 1) {
            flag[i] = 1;
            order[idx] = num[i];
            com[idx-1] = '+';
            if(dfs(num, flag, result + num[i], com, order)) {
                return 1;
            }
            com[idx-1] = '-';
            if(dfs(num, flag, result - num[i], com, order)) {
                return 1;
            }
            com[idx-1] = '*';
            if(dfs(num, flag, result * num[i], com, order)) {
                return 1;
            }
            com[idx-1] = '/';
            debug("%d / %d\n",result,num[i]);
            if(result % num[i] == 0 && dfs(num, flag, result / num[i], com, order)) {
                return 1;
            }
            flag[i] = 0;
        }
    }
    return 0;
}

优化一下，还是借助深度搜索的想法，

先检查是否满足退出，不退出则把每个符号深度走一下。