深搜dfs
测试用例有问题,24点会有多组解的可能,通过65%,还看不到测试用例,好坑,本地测试ac。
#include <iostream>
#include<string>
#include<string.h>
#include <algorithm>
using namespace std;
int num[4];
int signal;
string operations = "+-*/";
bool dfs(int start,int sum)
{
if (start==4&&sum == 24)
{
signal = 1;
for (int i = 0; i < 3; i++)
{
cout << num[i] << operations[i];
}
cout << num[3] << endl;
return true;
}
for (int i =start; i < 4; i++)
{
if (!signal) {
operations[start - 1] = '+';
dfs(start + 1, sum + num[start]);
}
if (!signal) {
operations[start - 1] = '-';
dfs(start + 1, sum - num[start]);
}
if (!signal) {
operations[start - 1] = '*';
dfs(start + 1, sum * num[start]);
}
if (!signal) {
operations[start - 1] = '/';
dfs(start + 1, sum / num[start]);
}
}
return signal;
}
int main()
{
string str[4], strData = " A234567891JQK";
while (cin>>str[0]>> str[1] >> str[2] >> str[3] )
{
int error = 0;
signal = 0;
for (int i=0;i<4;i++)
{
if (str[i] == "10") num[i] = 10;
else
if (strData.npos == strData.find(str[i]))
{
error = 1;
cout << "ERROR" << endl;
break;
}
else num[i] = strData.find_first_of(str[i]);
}
if (!error)
{
do
{
if (dfs(1, num[0])) break;
} while (next_permutation(num, num + 4));
if (!signal) cout << "NONE" << endl;
}
}
return 0;
}
京公网安备 11010502036488号