poj3414Pots（BFS）

六种情况搜一下
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 struct node
  6 {
  7     int ca,cb;
  8     int flag,num;
  9     int op,ob;
 10 }q[1000000];
 11 int a,b,c,vis[110][110],num[100000],g;
 12 void put(int x,int y)
 13 {
 14     int yy;
 15     if(y==1)
 16     yy = 2;
 17     else
 18     yy = 1;
 19     if(x==1)
 20         printf("FILL(%d)\n",y);
 21     else
 22     if(x==3)
 23         printf("POUR(%d,%d)\n",y,yy);
 24     else
 25         printf("DROP(%d)\n",y);
 26 }
 27 void bfs()
 28 {
 29     int p = 0,d = 1,na,nb,flag = 0;
 30     memset(vis,0,sizeof(vis));
 31     q[d].ca = 0;
 32     q[d].cb = 0;
 33     q[d].num = 0;
 34     q[d].flag = -1;
 35     g = 0;
 36     while(p!=d)
 37     {
 38         p++;
 39         int ta = q[p].ca;
 40         int tb = q[p].cb;
 41         int tnum = q[p].num;
 42         if(ta==c||tb==c)
 43         {
 44             flag = 1;
 45             break;
 46         }
 47         if(ta!=a)
 48         {
 49             na = a;
 50             nb = tb;
 51             if(!vis[na][nb])
 52             {
 53                 d++;
 54                 q[d].ca = na;
 55                 q[d].cb = nb;
 56                 q[d].flag = p;
 57                 q[d].op = 1;
 58                 q[d].ob = 1;
 59                 q[d].num = tnum+1;
 60                 vis[na][nb] = 1;
 61             }
 62         }
 63         if(tb!=b)
 64         {
 65             nb = b;
 66             na = ta;
 67             if(!vis[na][nb])
 68             {
 69                 d++;
 70                 q[d].ca = na;
 71                 q[d].cb = nb;
 72                 q[d].flag = p;
 73                 q[d].op = 1;
 74                 q[d].ob = 2;
 75                 q[d].num = tnum+1;
 76                 vis[na][nb] = 1;
 77             }
 78         }
 79         if(ta!=0)
 80         {
 81             nb = tb;
 82             na = 0;
 83             if(!vis[na][nb])
 84             {
 85                 d++;
 86                 q[d].ca = na;
 87                 q[d].cb = nb;
 88                 q[d].flag = p;
 89                 q[d].op = 2;
 90                 q[d].ob = 1;
 91                 q[d].num = tnum+1;
 92                 vis[na][nb] = 1;
 93             }
 94         }
 95         if(tb!=0)
 96         {
 97             nb = 0;
 98             na = ta;
 99             if(!vis[na][nb])
100             {
101                 d++;
102                 q[d].ca = na;
103                 q[d].cb = nb;
104                 q[d].flag = p;
105                 q[d].op = 2;
106                 q[d].ob = 2;
107                 q[d].num = tnum+1;
108                 vis[na][nb] = 1;
109             }
110         }
111         if(tb!=b&&ta!=0)
112         {
113             if(ta+tb<=b)
114             {
115                 na = 0;
116                 nb = ta+tb;
117             }
118             else
119             {
120                 nb = b;
121                 na = ta-(b-tb);
122             }
123             if(!vis[na][nb])
124             {
125                 d++;
126                 q[d].ca = na;
127                 q[d].cb = nb;
128                 q[d].flag = p;
129                 q[d].op = 3;
130                 q[d].ob = 1;
131                 q[d].num = tnum+1;
132                 vis[na][nb] = 1;
133             }
134         }
135         if(ta!=a&&tb!=0)
136         {
137             if(tb+ta<=a)
138             {
139                 nb = 0;
140                 na = tb+ta;
141             }
142             else
143             {
144                 na = a;
145                 nb = tb-(a-ta);
146             }
147             if(!vis[na][nb])
148             {
149                 d++;
150                 q[d].ca = na;
151                 q[d].cb = nb;
152                 q[d].flag = p;
153                 q[d].op = 3;
154                 q[d].ob = 2;
155                 q[d].num = tnum+1;
156                 vis[na][nb] = 1;
157             }
158         }
159     }
160     if(flag)
161     {
162         cout<<q[p].num<<endl;
163         int x = p;
164         while(x!=1)
165         {
166             g++;
167             num[g] = x;
168             x = q[x].flag;
169         }
170     }
171     else
172     puts("impossible");
173 }
174 int main()
175 {
176     int i;
177     while(cin>>a>>b>>c)
178     {
179         bfs();
180         for(i = g ; i >= 1; i--)
181         put(q[num[i]].op,q[num[i]].ob);
182     }
183     return 0;
184 }