题解 | #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;
}
全部评论

相关推荐

09-03 14:50
长春大学 Java
牛客407945238号:这环境…怎么看都像是低配版的电诈园区
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务