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

79愛的鼓勵 1訂閱站台

作法 : DFS

我個人認為多重解不夠多
硬湊到AC (程式碼1)

程式碼2(WA) 但是我認為這比較好

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

#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[10000][2],ans[10000][2],min;  
int record[201][201];  
int Ca,Cb,N,find=0;  
void WaterJug(int now,int Ca,int Cb,int A,int B,int goal)  
{  
   if(record[Ca][Cb]==1) return;  
   record[Ca][Cb]=1;  
   steps[now][0]=Ca;  
   steps[now][1]=Cb;  
   int a,b,c;  
   if(Ca+Cb==goal)  
      {  
        if(now<min)   
          {  
             for(a=1;a<=now;a++)  
                {  
                 ans[a][0]=steps[a][0];ans[a][1]=steps[a][1];  
                }   
             min=now;  
          }   
        return;  
      }     
 
   if(Cb!=0)  
        {   
         WaterJug(now+1,Ca,0,A,B,goal);/*倒掉B*/ 
           
         if(Ca!=A)   
            {/*將B倒入A*/   
               int temp=A-Ca;/*A剩餘容量*/   
               if(Cb>temp) /*B倒完還有剩*/   
                  WaterJug(now+1,A,Cb-temp,A,B,goal);  
               else  WaterJug(now+1,Ca+Cb,0,A,B,goal);  
            }  
        }     
   if(Ca!=0)  
        {   
         WaterJug(now+1,0,Cb,A,B,goal);/*倒掉A*/   
            
          if(Cb!=B)   
            {/*將A倒入B*/   
               int temp=B-Cb;/*B剩餘容量*/   
               if(Ca>temp) /*A倒完還有剩*/ 
                  WaterJug(now+1,Ca-temp,B,A,B,goal);  
               else  WaterJug(now+1,0,Cb+Ca,A,B,goal);  
            }   
        }    
   if(Ca<A) /*裝滿A*/ 
         WaterJug(now+1,A,Cb,A,B,goal);  
   if(Cb<B) /*裝滿B*/ 
         WaterJug(now+1,Ca,B,A,B,goal);  
 
}  
main()  
{  
   while(scanf("%d %d %d",&Ca,&Cb,&N)==3)  
       {  
          int a,b;  
          for(a=0;a<=200;a++)  
             for(b=0;b<=200;b++)  
                record[a][b]=0;  
          min=20000;   
          if(N%GCD(Ca,Cb)==0&&N<=Ca+Cb)  
          {   
                WaterJug(0,0,0,Ca,Cb,N);  
                printf("(0,0)");  
                for(a=1;a<=min;a++)  
                   printf(" -> (%d,%d)",ans[a][0],ans[a][1]);  
                 printf("\n");  
           }   
          else 
             printf("NO\n");  
       }  
  return 0;  
} 

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

#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[10000][2],ans[10000][2],min;     
int record[201][201];     
int Ca,Cb,N,find=0;     
void WaterJug(int now,int Ca,int Cb,int A,int B,int goal)     
{     
   if(record[Ca][Cb]<now||now>min) return;     
   record[Ca][Cb]=now;
   steps[now][0]=Ca;
   steps[now][1]=Cb;
   int a,b,c;
   if(Ca+Cb==goal)
      {     
        if(now<min)      
          {     
             for(a=1;a<=now;a++)     
                {     
                 ans[a][0]=steps[a][0];ans[a][1]=steps[a][1];     
                }      
             min=now;     
          }      
        return;     
      }        
     if(Cb!=0)     
        {      
         WaterJug(now+1,Ca,0,A,B,goal);/*倒掉B*/    
              
         if(Ca!=A)      
            {/*將B倒入A*/      
               int temp=A-Ca;/*A剩餘容量*/      
               if(Cb>temp) /*B倒完還有剩*/      
                  WaterJug(now+1,A,Cb-temp,A,B,goal);     
               else  WaterJug(now+1,Ca+Cb,0,A,B,goal);     
            }     
        } 
   if(Ca!=0)     
        {      
         WaterJug(now+1,0,Cb,A,B,goal);/*倒掉A*/      
               
          if(Cb!=B)      
            {/*將A倒入B*/      
               int temp=B-Cb;/*B剩餘容量*/      
               if(Ca>temp) /*A倒完還有剩*/    
                  WaterJug(now+1,Ca-temp,B,A,B,goal);     
               else  WaterJug(now+1,0,Cb+Ca,A,B,goal);     
            }      
        }
   if(Ca<A) /*裝滿A*/    
         WaterJug(now+1,A,Cb,A,B,goal);     
   if(Cb<B) /*裝滿B*/    
         WaterJug(now+1,Ca,B,A,B,goal);  
 
        
}     
main()     
{     
   while(scanf("%d %d %d",&Ca,&Cb,&N)==3)     
       {     
          int a,b;     
          for(a=0;a<=Ca;a++)     
             for(b=0;b<=Cb;b++)     
                record[a][b]=150;
          min=150;      
          if(N%GCD(Ca,Cb)==0&&N<=Ca+Cb)     
          {      
                WaterJug(0,0,0,Ca,Cb,N);     
                printf("(0,0)");     
                for(a=1;a<=min;a++)     
                   printf(" -> (%d,%d)",ans[a][0],ans[a][1]);     
                 printf("\n");     
           }      
          else    
             printf("NO\n");     
       }     
  return 0;     
}