摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 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;
}