poj_1606_回溯

题目描述：

解题思路：

代码：

#include <stdio.h>
#include <stdlib.h>
#define N 1000

char print_str[6][20] = {{"pour A B"},{"pour B A"},{"fill B"},{"fill A"},{"empty B"},{"empty A"}};
int a, b, n, count, result[N], current[2], flag[N][N];

int find()
{
   int c[2],tmp, i, f;
   if(current[0]==0 && current[1]==0){
      return 1;
   }else{
      f = 0;
      flag[current[0]][current[1]] = 1;
      c[0] = current[0];
      c[1] = current[1];
      //pour A B
      if((current[0]<a && current[1]==b)||(current[0]==0)){
         if(current[0]!=0){
             tmp = a - current[0];
             current[0] = a;
             current[1] = b-tmp;
         }else{
            if(current[0]+current[1]<a){
               current[0] = current[1];
               current[1] = 0;
            }else{
               current[1] =  current[1] - a;
               current[0] = a;
            }
         }
         result[count] = 0;
         count ++;
         if(flag[current[0]][current[1]] == 0){
            f = find();
            if(f)
               return f;
            flag[current[0]][current[1]] = 0;
         }
         current[0] = c[0];
         current[1] = c[1];
         count --;
      }
      //pour B A
      if((current[0]==a && current[1]<b)||(current[1]==0)){
         if(current[1]!=0){
             if(current[0]+current[1]<=b){
                current[1] = current[0] + current[1];
                current[0] = 0;
             }else{
                 tmp = b - current[1];
                 current[1] = b;
                 current[0] = a - tmp;
             }
         }else{
            current[1] = current[0];
            current[0] = 0;
         }
         if(current[0]>=0){
             result[count] = 1;
             count ++;
             if(flag[current[0]][current[1]] == 0){
                f = find();
                if(f)
                   return f;
                 flag[current[0]][current[1]] = 0;
             }
             count --;
           
         }
         current[0] = c[0];
         current[1] = c[1];
      }
      //fill B
      if(f==0 && (current[1] == b)){
         result[count] = 2;
         for(i=0;i<b;i++){
            current[1]=i;
            count ++;
            if(flag[current[0]][current[1]] == 0){
               f = find();
               if(f)
                  return f;
               flag[current[0]][current[1]] = 0;
            }
           
            current[0]=c[0];
            count--;
         }
      }
      //fill A
      if(current[0] == a){
         result[count] = 3;
        
         for(i=0;i<a;i++){
            current[0]=i;
            count ++;
            if(flag[current[0]][current[1]] == 0){
               f = find();
               if(f)
                  return f;
               flag[current[0]][current[1]] = 0;
            }
           
            current[1]=c[1];
            count--;
         }
      }
      //empty B
      if(current[1] == 0){
         result[count] = 4;
         for(i=1;i<=b;i++){
            current[1] = i;
            count++;
            if(flag[current[0]][current[1]] == 0){
               f = find();
               if(f)
                  return f;
               flag[current[0]][current[1]] = 0;
            }
           
            current[0] = c[0];
            count --;
         }
      }
      //empty A
      if(current[0] == 0){
         result[count] = 5;
         for(i=1;i<=a ;i++){
            current[0] = i;
            count ++;
            if(flag[current[0]][current[1]] == 0){
               f = find();
               if(f)
                  return f;
            flag[current[0]][current[1]] = 0;
            }
           
            current[1] = c[1];
            count --;
         }
      }
      return f;
   }  
}

main()
{    
   int f, i;
  
   while(scanf("%d %d %d",&a, &b, &n)!=EOF){
       memset(flag, 0, sizeof(flag));
       current[0] = 0;
       current[1] = n;
       f = find();
       if(!f){
           current[0] = a;
           current[1] = n;
           f = find();
       }  
       for(i=count-1;i>=0;i--)
          printf("%s\n",print_str[result[i]]);
       printf("success\n");
       count = 0;
   }
   //system("pause");
   return 0;
}