HDU 1427-速算24点(DFS)

速算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

思路：赤裸裸的爆搜。暴力搜索全排列，需要注意使用全排列前要排个序。（忘了，调好久......）

注意一下如何处理括号的优先级：只有4个数，所以最多有2对括号，也就是说这个表达式分成内外2部分，从这一点入手，在暴力的时候分一下。在原先的4则运算下再加一个分开的优先运算即可。详情见代码

代码如下：

#include<set>
#include<map>
#include<list>
#include<deque>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<stdlib.h>
#include<string.h>
//#include<ext/rope>
#include<iostream>
#include<algorithm>
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define per(i,a,b) for(int i=a;i<=b;++i)
#define LL long long 
#define swap(a,b) {int t=a;a=b;b=t} 
using namespace std;
//using namespace __gnu_cxx;
int p[4],fag=0;
void fun(char a,char b,int x)
{
	if(a=='A') p[x]=1;
	else if(a=='J') p[x]=11;
	else if(a=='Q') p[x]=12;
	else if(a=='K') p[x]=13;
	else if(a=='1'&&b=='0') p[x]=10;
	else p[x]=a-'0';
}
void dfs(int x,int y,int z)
{
	if(fag==1) return ;
	if(x==3) 
	{
		if(y+z==24) fag=1;
		if(y-z==24) fag=1;
		if(y*z==24) fag=1;
		if(z!=0&&y%z==0&&y/z==24) fag=1;
		return ;
	}
	dfs(x+1,y+z,p[x+1]);
	dfs(x+1,y-z,p[x+1]);
	dfs(x+1,y*z,p[x+1]);
	if(z!=0&&y%z==0) dfs(x+1,y/z,p[x+1]);
	dfs(x+1,y,z+p[x+1]);
	dfs(x+1,y,z-p[x+1]);
	dfs(x+1,y,z*p[x+1]);
	if(p[x+1]!=0&&z%p[x+1]==0) dfs(x+1,y,z/p[x+1]);
}
int main()
{
	string a,b,c,d;
	while(cin>>a>>b>>c>>d)
	{ 
	    fag=0;
	    fun(a[0],a[1],0);fun(b[0],b[1],1);
	    fun(c[0],c[1],2);fun(d[0],d[1],3);
	    sort(p,p+4);
	    do{
	    	dfs(1,p[0],p[1]);
		}while(next_permutation(p,p+4)&&fag==0);
	    if(fag==1) printf("Y\n");
	    else printf("N\n");
	}
	return 0;
}