C++

「搜索」RQNOJ 73 24点

RQNOJ 73 题目链接

题目描述

superwyh是一个非常疯狂的24点爱好者,空闲时总是自己拿出扑克来算24点,24点的规则很简单,就是给你4张扑克(从1至13,用A代替1,J代替11,Q代替12,K代替13)通过加减乘除来求得24,各位oier帮了superwyh好多忙,为了报答大家superwyh就和大家做个24点的游戏,superwyh给大家4张牌大家告诉superwyh能不能凑成24就行。

样例输入

A 2 3 4

###样例输出

yes

题解

这道题很有意思,主要看思路细致程度,深搜的题,但是有括号优先级需要处理,具体见代码:

/*
rqnoj 73 24点
如果能凑出24输出yes,否则no:input A 2 3 4  output yes
深搜题,见代码
*/
#include <iostream>
#include <cstring>
using namespace std;
string c;
int a[5];
bool vis[5];
bool dfs(int dep,double amount){
    if(dep==4){
        if(23.999999<amount&&amount<24.000001) return 1;
        else return 0;
    }
    for(int i=1;i<=4;i++){
        if(!vis[i]){
            vis[i]=1;
            if(dfs(dep+1,amount+a[i])) return 1;
            if(dfs(dep+1,amount-a[i])) return 1;
            if(dfs(dep+1,a[i]-amount)) return 1;
            if(amount!=0 && dfs(dep+1,amount*a[i])) return 1;
            if(amount!=0 && dfs(dep+1,amount/a[i])) return 1;
            if(amount!=0 && dfs(dep+1,a[i]/amount)) return 1;
            vis[i]=0;
        }
    }
    return 0;
}
int main(){
    for(int i=1;i<=4;i++){
        cin>>c;
        if(c[0]=='A'){a[i]=1;continue;}
        if(c[0]=='J'){a[i]=11;continue;}
        if(c[0]=='Q'){a[i]=12;continue;}
        if(c[0]=='K'){a[i]=13;continue;}
        if(c[0]=='1' && c[1]=='0'){a[i]=10;continue;}
        a[i]=c[0]-'0';
    }
    //debug: for(int i=1;i<=4;i++) cout<<a[i]<<" ";
    if(dfs(0,0)) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
    return 0;
}
分享到