ACM 10400 Q10400: Game Show Math
作法 : DFS
題目給的CUT,一定要用 >=32000 <=-32000 不要做
另外重複的路徑不要走.
/*******************************************************/
#include<stdio.h>
#include<stdlib.h>
int num[101]={0};
int tol[101]={0},find,goal;
int n,m,a,b,c,p;
int record[101][64001]={0};
void DFS (int now,int value)
{
int a;
if(find==1) return;
if(now==p-1)
{
if(value==goal)
{
find=1;
printf("%d",num[0]);
for(a=0;a<p-1;a++)
{
if(tol[a]==1) printf("+");
if(tol[a]==2) printf("-");
if(tol[a]==3) printf("*");
if(tol[a]==4) printf("/");
printf("%d",num[a+1]);
}
printf("=%d\n",goal);
}
return;
}
else
for(a=1;a<=4;a++)
{
tol[now]=a;
if(a==1&&value+num[now+1]<32000&&record[now+1][value+num[now+1]+32000]==0)
{
record[now+1][value+num[now+1]+32000]=1;
DFS(now+1,value+num[now+1]);
}
else if(a==2&&value-num[now+1]>-32000&&record[now+1][value-num[now+1]+32000]==0)
{
record[now+1][value-num[now+1]+32000]=1;
DFS(now+1,value-num[now+1]);
}
else if(a==3&&value*num[now+1]<32000&&value*num[now+1]>-32000&&record[now+1][value*num[now+1]+32000]==0)
{
record[now+1][value*num[now+1]+32000]=1;
DFS(now+1,value*num[now+1]);
}
else if(a==4&&num[now+1]!=0&&value%num[now+1]==0&&record[now+1][value/num[now+1]+32000]==0)
{
record[now+1][value/num[now+1]+32000]=1;
DFS(now+1,value/num[now+1]);
}
}
}
main()
{
while(scanf("%d",&n)==1)
while(n--)
{
scanf("%d",&p);
for(a=0;a<p;a++)
scanf("%d",&num[a]);
for(a=0;a<p;a++)
for(b=0;b<64000;b++)
record[a][b]=0;
scanf("%d",&goal);
find=0;
DFS(0,num[0]);
if(find==0)
printf("NO EXPRESSION\n");
}
return 0;
}