#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int len;
int a, b, c;
bool visite[1001][1001],ok;
int front, rear;
struct Node{
int a, b,front;
char oper;
Node(){}
Node( int m, int n):a(m),b(n){}
Node( int m, int n, int c, char d ): a(m),b(n),front(c),oper(d) {}
};
Node queue[65535];
void bfs()
{
front= -1, rear= 0;
queue[0]= Node(0, 0, -1, 'z');
while( front< rear )
{
front++;
Node t= queue[front];
if( t.b== c ) {
len= front;
return; }
int m= t.a, n= t.b;
if( m> 0 && !visite[0][n] ) { queue[++rear]= Node( 0, n, front, 'a' ); visite[0][n]= true; } // empty A
if( n> 0 && !visite[m][0] ) { queue[++rear]= Node( m, 0, front, 'b' ); visite[m][0]= true; } // empty B
if( m!= a && n> a- m && !visite[a][n+m-a] ) { // pour B to A
queue[++rear]= Node( a, n+ m- a, front, 'c' ); visite[a][n+m-a]= true; }
else if( m!= a && n> 0 && m+ n<= a && !visite[m+n][0] ){
queue[++rear]= Node( m+ n, 0, front, 'c' ); visite[m+n][0]= true; }
if( n!= b && m> b- n && !visite[m+n-b][b] ){ // pour A to B
queue[++rear]= Node( n+ m- b, b, front, 'd' ); visite[m+n-b][b]= true; }
else if( n!= b && m> 0 && n+ m<= b && !visite[0][m+n] ){
queue[++rear]= Node( 0, m+ n, front, 'd' ); visite[0][m+n]= true; }
if( m!= a && !visite[a][n] ) { queue[++rear]= Node( a, n, front, 'e' ); visite[a][n]= true; } // fill A
if( n!= b && !visite[m][b] ) { queue[++rear]= Node( m, b, front, 'f' ); visite[m][b]= true; } // fill B
}
}
void print( int n )
{
if( n== 0 ) return;
print( queue[n].front );
switch( queue[n].oper)
{
case 'a': puts("empty A"); break;
case 'b': puts("empty B"); break;
case 'c': puts("pour B A"); break;
case 'd': puts("pour A B"); break;
case 'e': puts("fill A"); break;
case 'f': puts("fill B"); break;
}
}
int main()
{
while( scanf("%d%d%d", &a, &b, &c)!= EOF )
{
memset( visite, false, sizeof(visite) );
visite[0][0]= true;
bfs();
print( len );
puts("success");
}
return 0;
}
posted on 2008-11-14 22:43
Darren 閱讀(535)
評論(1) 編輯 收藏 引用