题解 | #24点运算# 暴力DFS
24点运算
http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d
思路:
根据输入字符串得到一个数组Vec,之后根据这个Vec进行深搜。深搜的时候为避免麻烦的回溯,将Vec深拷贝后再进行erase操作即可。保存答案的ans字符串也同理,先深拷贝再修改。将所有符合条件的ans push到一个结果数组中,最后输出第一个即可。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
string ItoString(int i);
void DFS(vector<int>& Vec,int combined,string& ans,vector<string>& result){
if(Vec.size()==0){
if(combined!=24)
return;
else{
result.emplace_back(ans);
return;
}
}
for(int i=0;i<Vec.size();i++){
vector<int> temp(Vec);
temp.erase(temp.begin()+i);
string anstemp(ans);
anstemp+='+';
anstemp+=ItoString(Vec[i]);
DFS(temp,combined+Vec[i],anstemp,result);
anstemp=ans;
anstemp+='*';
anstemp+=ItoString(Vec[i]);
DFS(temp,combined*Vec[i],anstemp,result);
anstemp=ans;
anstemp+='-';
anstemp+=ItoString(Vec[i]);
DFS(temp,combined-Vec[i],anstemp,result);
anstemp=ans;
anstemp+='/';
anstemp+=ItoString(Vec[i]);
DFS(temp,combined/Vec[i],anstemp,result);
anstemp=ans;
}
}
string ItoString(int i){
string ret;
if(2<=i&&i<=9){
ret=(char)('0'+i);
}
else if(i==11){
ret="J";
}
else if(i==1){
ret="A";
}
else if(i==12){
ret="Q";
}
else if(i==13){
ret="K";
}
else if(i==10){
ret="10";
}
return ret;
}
int main(){
string input;
while(getline(cin,input)){
if(input.find("joker")!=string::npos||input.find("JOKER")!=string::npos){
cout<<"ERROR"<<endl;
continue;
}
input+=' ';
int n=input.size();
vector<int> Vec;
int temp=0;
for(int i=0;i<n;i++){
if('0'<=input[i]&&input[i]<='9'){
temp*=10;
temp+=(input[i]-'0');
}
else if(input[i]==' '){
Vec.push_back(temp);
temp=0;
}
else if(input[i]=='J'){
temp=11;
}
else if(input[i]=='Q'){
temp=12;
}
else if(input[i]=='K'){
temp=13;
}
else if(input[i]=='A'){
temp=1;
}
}
int combined=0;
vector<string> result;
for(int i=0;i<Vec.size();i++){
vector<int> temp(Vec);
string ans="";
temp.erase(temp.begin()+i);
ans+=ItoString(Vec[i]);
DFS(temp,Vec[i],ans,result);
}
if(result.size()!=0){
cout<<result[0];
}
else
cout<<"NONE";
}
return 0;
}