c++ 回溯算法,回溯的是一个map,用来记录用过的牌

24点运算

http://www.nowcoder.com/questionTerminal/7e124483271e4c979a82eb2956544f9d

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
string pukef(int x) {
	if (x >= 2 && x <= 10) {
		return to_string(x);
	}
	switch (x) {
	case 1:
		return "A";
		break;
	case 11:
		return "J";
		break;
	case 12:
		return "Q";
		break;
	case 13:
		return "K";
		break;

	default:
		break;
	}
}
int puke(string x) {
	if (x.size() == 1) {
		if (x.front() >= '2' && x.front() <= '9') {
			return stoi(x);
		}
		switch (x.front()) {
		case 'A':
			return 1;
			break;
		case 'J':
			return 11;
			break;
		case 'Q':
			return 12;
			break;
		case 'K':
			return 13;
			break;
		default:
			break;
		}
	} else if (x == "10") {
		return 10;
	} else
		return 0;

}
bool ok;

void dfs(string &s, int &ans, unordered_map<int, int> &us, vector<int> &v,
		unordered_map<int, int> &vs) {
	int ci = 0;
	for (auto &i : us) {
		ci += i.second;
	}
	if (ci == 4) {
		if (ans == 24) {
			cout << s.substr(1) << endl;
			ok = 1;
			return;
		}
		return;
	}
	s.push_back('+');
	for (int var = 0; var < v.size(); ++var) {
		if (us[v.at(var)] < vs[v.at(var)]) {
			string n = pukef(v.at(var));
			s += n;
			ans += v.at(var);
			us[v.at(var)]++;
			dfs(s, ans, us, v, vs);
			if (ok) {
				return;
			}
			ans -= v.at(var);
			us[v.at(var)]--;
			s.erase(s.size() - n.size());
		}
	}
	s.pop_back();
	s.push_back('-');
	for (int var = 0; var < v.size(); ++var) {
		if (us[v.at(var)] < vs[v.at(var)]) {
			string n = pukef(v.at(var));
			s += n;
			ans -= v.at(var);
			us[v.at(var)]++;
			dfs(s, ans, us, v, vs);
			if (ok) {
				return;
			}
			ans += v.at(var);
			us[v.at(var)]--;
			s.erase(s.size() - n.size());
		}
	}
	s.pop_back();
	s.push_back('*');
	for (int var = 0; var < v.size(); ++var) {
		if (us[v.at(var)] < vs[v.at(var)]) {
			string n = pukef(v.at(var));
			s += n;
			ans *= v.at(var);
			us[v.at(var)]++;
			dfs(s, ans, us, v, vs);
			if (ok) {
				return;
			}
			ans /= v.at(var);
			us[v.at(var)]--;
			s.erase(s.size() - n.size());
		}
	}
	s.pop_back();
	s.push_back('/');
	for (int var = 0; var < v.size(); ++var) {
		if (us[v.at(var)] < vs[v.at(var)] && ans / v.at(var) >= 2
				&& ans % v.at(var) == 0) {

			string n = pukef(v.at(var));
			s += n;
			ans /= v.at(var);
			us[v.at(var)]++;
			dfs(s, ans, us, v, vs);
			if (ok) {
				return;
			}
			ans *= v.at(var);
			us[v.at(var)]--;
			s.erase(s.size() - n.size());
		}
	}
	s.pop_back();
}

int main() {
	string a, b, c, d;
	while (cin >> a >> b >> c >> d) {
		int ai = puke(a);
		int bi = puke(b);
		int ci = puke(c);
		int di = puke(d);
		if (ai && bi && ci && di) {
			string s { "" };
			int ans = 0;
			unordered_map<int, int> us;
			vector<int> v { ai, bi, ci, di };
			unordered_map<int, int> vs;
			for (auto &i : v) {
				vs[i]++;
			}
			dfs(s, ans, us, v, vs);
			if (!ok) {
				cout << "NONE" << endl;
			}
		} else {
			cout << "ERROR" << endl;
		}
	}
	return 0;
}
注意除法
注意牌可以重复
注意输出牌面符号
全部评论
这么长,考试时候真能写出来么
点赞 回复 分享
发布于 2021-12-19 01:13

相关推荐

评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务