作法 : DFS

必須利用陣列作標記

假如這個方法已經試過了,且步驟次數沒有比較小 則不繼續搜下去

/*********************************************************/

#include <stdlib.h>     
#include <stdio.h>     
int GCD(int a,int b)     
{     
  int temp;     
  while(a%b)     
     {     
        temp=a;     
        a=b;     
        b=temp%b;     
     }     
  return b;     
}     
/*int steps[100000][3],ans[100000][3];    */ 
unsigned char record[101][101][101],min;     
int Ca,Cb,N,find=0;     
void WaterJug(int now,int Ca,int Cb,int A,int B,int goal,int sum)     
{ 
   if(sum>goal||now>min) return;   
   if(record[Ca][Cb][sum]<=now) return;
   record[Ca][Cb][sum]=now;
  
  /* steps[now][0]=Ca;     
   steps[now][1]=Cb;
   steps[now][2]=sum;*/
  /* printf("(%d,%d,%d) %d\n",Ca,Cb,sum,now);*/
   int a,b,c;     
   if(sum==goal)     
      {
        if(now<min)      
          {     
            /* for(a=1;a<=now;a++)     
                {     
                 ans[a][0]=steps[a][0];ans[a][1]=steps[a][1];ans[a][2]=steps[a][2];
                }       */
             min=now;     
          }      
        return;     
      }  
   if(Ca<A) /*裝滿A*/    
         WaterJug(now+1,A,Cb,A,B,goal,sum);
   if(Cb<B) /*裝滿B*/    
         WaterJug(now+1,Ca,B,A,B,goal,sum);  
   if(Cb!=0) WaterJug(now+1,Ca,0,A,B,goal,sum+Cb);/*B倒入 N*/
   if(Ca!=0) WaterJug(now+1,0,Cb,A,B,goal,sum+Ca);/*A倒入 N*/         
  
   if(Ca!=0)     
        {
         WaterJug(now+1,0,Cb,A,B,goal,sum);/*倒掉A*/
        
          if(Cb!=B)      
            {/*將A倒入B*/      
               int temp=B-Cb;/*B剩餘容量*/      
               if(Ca>temp) /*A倒完還有剩*/    
                  WaterJug(now+1,Ca-temp,B,A,B,goal,sum);     
               else  WaterJug(now+1,0,Cb+Ca,A,B,goal,sum);     
            }      
        }
 
   if(Cb!=0)     
        {
         WaterJug(now+1,Ca,0,A,B,goal,sum);/*倒掉B*/    
         if(Ca!=A)      
            {/*將B倒入A*/      
               int temp=A-Ca;/*A剩餘容量*/      
               if(Cb>temp) /*B倒完還有剩*/      
                  WaterJug(now+1,A,Cb-temp,A,B,goal,sum);     
               else  WaterJug(now+1,Ca+Cb,0,A,B,goal,sum);     
            }     
        }        
}     
main()     
{     
   while(scanf("%d %d %d",&Ca,&Cb,&N)==3)     
       {     
          if(Ca+Cb+N==0) break;
          int a,b,c;     
          for(a=0;a<=Ca;a++)
             for(b=0;b<=Cb;b++)     
                for(c=0;c<=N;c++)
                    record[a][b][c]=200;
          min=200;
          if(N%GCD(Ca,Cb)==0)     
          {      
                WaterJug(0,0,0,Ca,Cb,N,0);     
              /*  printf("(0,0,0)");     
                for(a=1;a<=min;a++)     
                   printf(" -> (%d,%d,%d)",ans[a][0],ans[a][1],ans[a][2]);     
                 printf("\n");*/
                printf("%d\n",min);
           }      
          else    
             printf("No\n");     
       }     
  return 0;     
}