hdu 1427 速算24点 dfs暴力搜索

速算24点

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。

Input

每组输入数据占一行，给定四张牌。

Output

每一组输入数据对应一行输出。如果有解则输出"Yes"，无解则输出"No"。

Sample Input

A 2 3 6
3 3 8 8

Sample Output

Yes
No

Author

LL

 思路：暴力搜索，利用next_permutation全排列

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 999999999
#define esp 0.00000000001
//#pragma comment(linker, "/STACK:102400000,102400000")
int scan()
{
    int res =  , ch ;
    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )
    {
        if( ch == EOF ) return  <<  ;
    }
    res = ch - '' ;
    while( ( ch = getchar() ) >= '' && ch <= '' )
        res = res *  + ( ch - '' ) ;
    return res ;
}
int a[];
int ans;
int getnum(string a)
{
    if(a[]=='')
    return ;
    if(a[]>=''&&a[]<='')
    return a[]-'';
    if(a[]=='A')
    return ;
    if(a[]=='J')
        return ;
    if(a[]=='K')
        return ;
    if(a[]=='Q')
    return ;
}
void dfs(int num,int gg,int step)
{
    if(step==)
    {
        if(num==)
        ans=;
        return;
    }
    //不加括号
    dfs(num+gg,a[step+],step+);
    dfs(num-gg,a[step+],step+);
    dfs(num*gg,a[step+],step+);
    if(gg!=&&num%gg==)
    dfs(num/gg,a[step+],step+);
    //加括号
    if(step!=)
    {
        dfs(num,gg+a[step+],step+);
        dfs(num,gg*a[step+],step+);
        dfs(num,gg-a[step+],step+);
        if(a[step+]!=&&gg%a[step+]==)
        dfs(num,gg/a[step+],step+);
    }
}
string ch[];
int main()
{
    int x,y,z,i,t;
    while(cin>>ch[]>>ch[]>>ch[]>>ch[])
    {
        ans=;
        for(i=;i<;i++)
        a[i]=getnum(ch[i]);
        sort(a,a+);
        do
        {
            dfs(a[],a[],);
        }
        while(next_permutation(a,a+));
        if(ans)
        printf("Yes\n");
        else
        printf("No\n");
    }
    return ;
}