python/TangDou/LanQiaoBei/LanQiao14STEMA202208/24.cpp

/* HDU1427 速算24点 */

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

using namespace std;

const int N = 4;
int a[N];
bool flag;

bool dfs(int cnt, int result1, int result2) {
    if (cnt == N - 1) {
        if (result1 + result2 == 24 || result1 - result2 == 24 || result1 * result2 == 24)
            flag = true;
        if (result2 != 0 && result1 % result2 == 0 && result1 / result2 == 24)
            flag = true;
    } else if (!flag) {
        // 先算前2项
        dfs(cnt + 1, result1 + result2, a[cnt + 1]);
        dfs(cnt + 1, result1 - result2, a[cnt + 1]);
        dfs(cnt + 1, result1 * result2, a[cnt + 1]);
        if (result2 != 0 && result1 % result2 == 0)
            dfs(cnt + 1, result1 / result2, a[cnt + 1]);

        // 先算后2项，相当与后2项计算是加括号的
        dfs(cnt + 1, result1, result2 + a[cnt + 1]);
        dfs(cnt + 1, result1, result2 - a[cnt + 1]);
        dfs(cnt + 1, result1, result2 * a[cnt + 1]);
        if (a[cnt + 1] != 0 && result2 % a[cnt + 1] == 0)
            dfs(cnt + 1, result1, result2 / a[cnt + 1]);
    }
    return false;
}

int main() {
    for (;;) {
        char s[4];
        for (int i = 0; i < N; i++) {
            if (scanf("%s", s) == EOF)
                return 0;
            if (strlen(s) == 2)
                a[i] = 10;
            else if (s[0] == 'A')
                a[i] = 1;
            else if (s[0] == 'J')
                a[i] = 11;
            else if (s[0] == 'Q')
                a[i] = 12;
            else if (s[0] == 'K')
                a[i] = 13;
            else
                a[i] = s[0] - '0';
        }

        sort(a, a + N);
        flag = false;
        do {
            dfs(1, a[0], a[1]);
            if (flag)
                break;
        } while (next_permutation(a, a + N));

        printf("%s\n", flag ? "Yes" : "No");
    }

    return 0;
}