经典的搜索题目,算24点,枚举四个数 枚举三个运算符,然后数和运算符的组合其实只有两种,分别判断一下,搜索还是不太熟悉,很多细节要考虑清楚
代码:
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-5;
bool vis[4];
int num[4];
int now[4];
int op[3];
int t;
double ope(double a,double b,int x){
switch(x){
case 1:{
return a+b;
}
case 2:{
return a-b;
}
case 3:{
return a*b;
}
case 4:{
if(fabs(b-0)>eps){
return a/b;
}
else{
return -0x3f3f3f3f;
}
}
case 5:{
return b-a;
}
case 6:{
if(fabs(a-0)>eps){
return b/a;
}
else{
return -0x3f3f3f3f;
}
}
}
}
//式子只有两种形式
double check1(){
return ope(ope(now[0],now[1],op[0]),ope(now[2],now[3],op[1]),op[2]);
}
double check2(){
return ope(ope(ope(now[0],now[1],op[0]),now[2],op[1]),now[3],op[2]);
}
bool calc(int dep){
//三个运算符枚举结束
if(dep==3){
if(fabs(check1()-24)<eps){
return true;
}
if(fabs(check2()-24)<eps){
return true;
}
return false;
}
//枚举运算符
for(int i=1;i<=6;i++){
op[dep]=i;
if(calc(dep+1)){
return true;
}
}
return false;
}
bool dfs(int dep){
//四个数字枚举结束
if(dep==4){
return calc(0);
}
//枚举数字
for(int i=0;i<4;i++){
if(!vis[i]){
vis[i]=true;
now[dep]=num[i];
if(dfs(dep+1)){
return true;
}
vis[i]=false;
}
}
return false;
}
int main(void){
scanf("%d",&t);
while(t--){
memset(vis,false,sizeof(vis));
scanf("%d%d%d%d",&num[0],&num[1],&num[2],&num[3]);
//从第一个数开始搜
if(dfs(0)){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}