题目描述:
24点是一个有趣的扑克牌游戏。发4张牌,然后计算是否能够算出24点来。(不考虑有括号的算式,输出计算式将从左到有进行计算)
如果可以,输出算数表达式;
如果不可以,输出NONE
如果表达式中,有错误输入,输出“ERROR”
输入实例:
2
AAAA
Q3J8
输出实例:
NONE
Q-J*3*8
代码解析:
下面解析,将以对其中一组数据(4个字符)为例
- main函数中读入字符串
- 先选择第一个数
- 开始深搜,一直到搜了四个数之后,判断是否为24,是就将更新答案,并返回True
- 进行选择,每一次深搜,都是选择一个运算符和一个数字(字符)。用tempAns来记录表达式。
- 注意要对深搜部分进行恢复,避免影响下一次深搜。同时用visited记录访问过的点,避免重复使用,并进入死循环。(答案错了就检查是不是没有深搜恢复好;出现死循环,很有可能是因为没有标记访问过的点)
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
char cards[4];
bool visited[4];
char cal[] = {'+', '-', '*', '/'};
string ans, tempAns;
double tempNum;
int charToNum(char c) {
if (c <= '9' && c>= '0') {
return c - '0';
} else if (c == 'J') {
return 11;
} else if (c == 'Q') {
return 12;
} else if (c == 'K') {
return 13;
} else if (c == 'A') {
return 1;
}
return -1;
}
bool DFS(int now) { // now From 1
if(now == 4) {
if (abs(tempNum - 24) < 1e-6) {
ans = tempAns;
return true;
}
return false;
}
// choose a cal
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (!visited[j]) {
if (i == 0) {
tempNum += charToNum(cards[j]);
visited[j] = true;
tempAns.push_back(cal[i]);
tempAns.push_back(cards[j]);
} else if (i == 1) {
tempNum -= charToNum(cards[j]);
visited[j] = true;
tempAns.push_back(cal[i]);
tempAns.push_back(cards[j]);
} else if (i == 2) {
tempNum *= charToNum(cards[j]);
visited[j] = true;
tempAns.push_back(cal[i]);
tempAns.push_back(cards[j]);
} else if (i == 3) {
tempNum /= charToNum(cards[j]);
visited[j] = true;
tempAns.push_back(cal[i]);
tempAns.push_back(cards[j]);
}
if(DFS(now + 1)) {
return true;
}
if (i == 0) {
tempNum -= charToNum(cards[j]);
visited[j] = false;
tempAns = tempAns.substr(0, tempAns.length() - 2);
} else if (i == 1) {
tempNum += charToNum(cards[j]);
visited[j] = false;
tempAns = tempAns.substr(0, tempAns.length() - 2);
} else if (i == 2) {
tempNum /= charToNum(cards[j]);
visited[j] = false;
tempAns = tempAns.substr(0, tempAns.length() - 2);
} else if (i == 3) {
tempNum *= charToNum(cards[j]);
visited[j] = false;
tempAns = tempAns.substr(0, tempAns.length() - 2);
}
}
}
}
return false;
}
int main(){
int time, fa;
cin >> time;
while(time--) {
char c;
fa = true;
for (int i = 0; i < 4; ++i){
cin >> c;
if (c <= '9' && c>= '0' || c == 'J' || c == 'Q' || c == 'K' || c == 'A') {
cards[i] = c;
} else {
fa = false;
}
}
if (!fa) {
cout << "Error!\n"; continue;
}
memset(visited, false, sizeof(visited));
bool ok = false;
for (int i = 0; i < 4; ++i) {
tempAns.clear();
visited[i] = true;
tempAns.push_back(cards[i]);
tempNum = charToNum(cards[i]);
if (DFS(1)){
cout<< ans<< endl;
ok = true;
break;
}
visited[i] = false;
}
if (!ok) {
cout << "NONE\n";
}
}
}