题解 | 24点游戏算法

// 轮盘+子轮盘 穷举，使用double保存中间值，以保证分数能正确运算
#include <functional>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
enum Op {
	None = 0,
	Add,
	Dec,
	Muti,
	Div,
	Max,
};
struct Expr;
// 表达式轮盘
struct ExprRound {
	vector<Expr*> _exprs;
	uint32_t _idx;
	uint32_t _last;
	ExprRound();
	~ExprRound();
	void Add(Expr* expr);
	double Init();
	bool GetVal(double& val);
};
struct Expr {
	bool _isVal;
	int _op;
	int _val;
	ExprRound _left;
	ExprRound _right;
	double _lVal;
	double _rVal;
	Expr();
	void Reset();
	~Expr();
	double Init();
	bool GetVal(double& val);
	void AddLeft(Expr* expr);
	void AddRight(Expr* expr);
	double MakeVal();
};

struct DigPairs {
	vector<int> v1;
	vector<int> v2;
};

void Split(int n, unordered_map<int, vector<DigPairs*>>& dict);

void MakeExpr(vector<Expr*>& all, vector<int>& dig, vector<int>& data);
ExprRound::ExprRound() {
	_idx = 0;
	_last = 0;
}
ExprRound::~ExprRound() {
	for(auto expr : _exprs) {
		delete expr;
	}
}
void ExprRound::Add(Expr* expr) {
	_exprs.push_back(expr);
}
double ExprRound::Init() {
	_idx = 0;
	_last = 0;
	double val;
	bool get = false;
	for(auto e : _exprs) {
		auto v = e->Init();
		if(!get) {
			val = v;
			get = true;
		}
	}
	return val;
}

bool ExprRound::GetVal(double &val) {
	// 当前子节点取完了
	_last = _idx;
	if(_exprs[_idx]->GetVal(val)) {
		_idx++;
		if(_idx >= _exprs.size()) {
			_idx = 0;
			return true;
		}
	}
	return false;
}

Expr::Expr() {
	_val = 0;
	Reset();
}

void Expr::Reset(){
	_op = Op::None;
	_lVal = 0;
	_rVal = 0;
}
Expr::~Expr() {
}
double Expr::Init() {
	if(_isVal) {
		return _val;
	}
	_lVal = _left.Init();
	_rVal = _right.Init();
	_op = Op::Add;
	return MakeVal();
}
bool Expr::GetVal(double& val) {
	if(_isVal) {
		val = _val;
		return true;
	}
	auto fin = false;
	do {
		_op++;
		if(_op == Op::Max) {
			_op = Op::Add;
		} else {
			break;
		}
		if(_left.GetVal(_lVal)) {
			if(_right.GetVal(_rVal)) {
				fin = true;
			}
		}
	}while(0);
	val = MakeVal();
	if(fin) {
		Init();
	}
	return fin;
}

void Expr::AddLeft(Expr* expr) {
	_left.Add(expr);
}
void Expr::AddRight(Expr* expr) {
	_right.Add(expr);
}
double Expr::MakeVal() {
	switch (_op) {
	case Op::Add:
		return _lVal + _rVal;
	case Op::Dec:
		return _lVal - _rVal;
	case Op::Muti:
		return _lVal * _rVal;
	case Op::Div:
		return _lVal / _rVal;
	default:
		return _val;
	}
}

void Split(int n, unordered_map<int, vector<DigPairs*>>& dict) {
	for(auto i = 1; i <= n/2; ++i) {
		auto& vec = dict[i];
		if(i == 1 ) {
			for(auto j = 0; j < n; ++j) {
				auto pair = new DigPairs();
				vec.push_back(pair);
				pair->v1.push_back(j);
				for(auto k = 0; k < n; ++k) {
					if(k == j) {
						continue;
					}
					pair->v2.push_back(k);
				}
			}
		} else {
			auto& pre = dict[i-1];
			for(auto pair : pre) {
				for(size_t j = 0; j < pair->v2.size(); ++j) {
					auto item = new DigPairs{pair->v1, pair->v2};
					item->v1.push_back(item->v2[j]);
					item->v2.erase(item->v2.begin() + j);
					vec.push_back(item);
				}
			}
		}
	}
}
// key:第一组的数量
using SplitDict = unordered_map<int, vector<DigPairs*>>;
// key:数字总数
unordered_map<int, SplitDict> gDict;

void MakeExpr(vector<Expr*>& all, vector<int>& dig, vector<int>& data) {
	if(dig.size() == 1) {
		auto item = new Expr();
		item->_isVal = true;
		item->_val = data[dig[0]];
		all.push_back(item);
		return;
	}
	vector<int> subData;
	subData.reserve(dig.size());
	for(auto v : dig) {
		subData.push_back(data[v]);
	}
	auto& dict = gDict[dig.size()];
	for(auto& it : dict) {
		for(auto pair : it.second) {
			auto item = new Expr();
			all.push_back(item);
			MakeExpr(item->_left._exprs, pair->v1, subData);
			MakeExpr(item->_right._exprs, pair->v2, subData);

			auto item2 = new Expr();
			all.push_back(item2);
			MakeExpr(item2->_left._exprs, pair->v2, subData);
			MakeExpr(item2->_right._exprs, pair->v1, subData);
		}
	}
}
int main() {
    for(auto i = 2; i <= 4; ++i) {
		Split(i, gDict[i]);
	}
	vector<int> dig = {0,1,2,3};
	vector<int> data;
	for(auto i = 0; i < 4; ++i) {
		int v;
		cin >> v;
		data.push_back(v);
	}
	vector<Expr*> all;
	MakeExpr(all, dig, data);
	int cnt = 0;
	for(auto expr : all) {
		double val = expr->Init();
		if(abs(val - 24) < 1e-6) {
			cout << "true" << endl;
			return 0;
		}
		while(true) {
			auto fin = expr->GetVal(val);
			++cnt;
			if(abs(val - 24) < 1e-6) {
				cout << "true" << endl;
				return 0;
			}
			if(fin) {
				break;
			}
		}
	}
	cout << "false" << endl;
}
// 64 位输出请用 printf("%lld")