题解 | 24点游戏算法

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
double arr[4];
inline bool is24(double& x) {
    return fabs(x - 24.0) < 1e-6;
}
vector<double> cal(double& a, double& b) {
    vector<double> ret = {a + b, a - b, b - a, a * b};
    if (b != 0.0)
        ret.push_back(a / b);
    if (a != 0.0)
        ret.push_back(b / a);
    return ret;
}
bool dfs(double res, int idx) {
    if (idx == 4)
        return is24(res);
    vector<double> next_res(cal(res, arr[idx]));
    for (double a : next_res)
        if (dfs(a, idx + 1))
            return true;
    return false;
}
bool dfs2() {
    vector<double> a(cal(arr[0], arr[1])), b(cal(arr[2], arr[3]));
    for (double i : a) {
        for (double j : b) {
            vector<double> c(cal(i, j));
            for (double k : c) {
                if (is24(k))
                    return true;
            }
        }
    }
    return false;
}
int main() {
    for (double& i : arr)
        cin >> i;
    sort(arr, arr + 4);
    do {
        if (dfs(arr[0], 1) || dfs2()) {
            cout << "true" << endl;
            return 0;
        }
    } while (next_permutation(arr, arr + 4));
    cout << "false" << endl;
    return 0;
}
// 64 位输出请用 prdoublef("%lld")