题解 | #24点运算#

使用DFS来做 在HJ67的基础上改进 具体步骤 1.将输入放入向量V，JKQA转成数字 2.DFS 注意res初值不能设为0，要遍历v[i]四个数字作为初值的情况，然后再往下递归查找 3.将out中记录的值做变换，从数字变回JKQA

#include <string>
#include <map>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
    map<string,int>m={{"3",3},{"4",4}
                     ,{"5",5},{"6",6}
                     ,{"7",7},{"8",8}
                     ,{"9",9},{"10",10}
                     ,{"J",11},{"Q",12}
                     ,{"K",13},{"A",1}
                     ,{"2",2}
                     };
bool flag = false;
void dfs(stack<string> s, int used,vector<int> v,float res,vector<string> &out ,vector<int> &b)
{
    if(flag ==true) return;
    if(used ==4)
    {
        if(res==24) 
        {    flag = true;
            while(s.size())
            {
                out.push_back(s.top());
                s.pop();
            }
        }
        return ;
    }

    
    
    for(int i=0;i<4;i++)
    {
        if(used==0)
        {
            res = v[i];
            
            b[i] = 1;
            s.push(to_string(v[i]));
            dfs(s, used+1, v, res, out, b);
            s.pop();
            b[i]=0;
            continue;
        }
       else if(b[i]==0&&used!=4)
        {
         if(flag ==false)   b[i] = 1;
            
            s.push("+"+to_string(v[i]));
            dfs(s, used+1, v, res+v[i], out, b);
            s.pop();
            s.push("-"+to_string(v[i]));
            dfs(s, used+1, v, res-v[i], out, b);
            s.pop();
            s.push("*"+to_string(v[i]));
            dfs(s, used+1, v, res*v[i], out, b);
            s.pop();
            s.push("/"+to_string(v[i]));
            dfs(s, used+1, v, res/v[i], out, b);
            s.pop(); 
           if(flag ==false)  b[i]  =0;
        } 
    }
    return ;
}

int main()
{
    string str;
    vector<int> v;
    while(cin>>str)
    {    
        if(str=="joker"||str=="JOKER") 
        {
            cout<<"ERROR"<<endl;
            return 0;
        }
        v.push_back(m[str]);    
    }
    stack<string> s;
    int used = 0;
    float res ;
    vector<string>out;
    vector<int> b(4,0);
    dfs(s, used, v, res, out, b);
    
    if(flag)
    {
        for(int i=0;i<out.size();i++)
        {
            
            if(out[i]=="13") out[i] ="K" ;
            if(out[i]=="12") out[i] ="Q" ; 
            if(out[i]=="11") out[i] ="J"  ;
            if(out[i]=="1") out[i] ="A" ; 
            string st;
            string fh;
            if(out[i].length()>=2)
            {
                st = out[i].substr(1,out[i].length()-1);
                fh = out[i].substr(0,1);
                if(st=="13") out[i] =fh+"K" ;
                if(st=="12") out[i] =fh+"Q" ; 
                if(st=="11") out[i] =fh+"J"  ;
                if(st=="1") out[i] =fh+"A" ; 
            }

            
            
        }
        
  
         
            cout << out[3]<<out[2]<<out[1]<<out[0];
        
            

    }
    else cout<<"NONE"<<endl;
    
}