POJ 3414

• 给两个杯子的容量,还有一个数代表最终容量,和6种操作,求出通过6中操作后 使得任意一个 杯子的容量等于最终容量,输出步数和操作的过程(保存bfs的路径),
• 用1~6代表每个6中操作,存在结构体中,bfs枚举6中操作,vis[i][j]存杯子中水容量的状态,
• DROP(i),如果i杯子为空,没有意义,POUR(a,b)根据杯子的大小来决定,

  #include <queue>
  #include <iostream>
  #include <string>
  #include <string.h>
  
  using namespace std;
  const int maxn = 101;
  
  struct node {
  	int a,b; // 存a,b的容量
  	int step;
  	string s;
  	node(){}
  	node(int a,int b,int s,string ch) {
  		this->a = a;
  		this->b = b;
  		this->step = s;
  		this->s = ch;
  	}
  };
  
  bool vis[maxn][maxn];
  int x;
  int liter[3];
  queue<node> que;
  string ans;
  
  void fill(int index,int& k) {
  	k = liter[index];
  }
  void pour(int indexa,int indexb,int& ka,int& kb) {
  	int temp = kb;
  	if (kb + ka <= liter[indexb]) {
  		kb += ka;
  	}
  	else {
  		kb = liter[indexb];
  	}
  	ka -= (kb - temp);
  }
  void drop(int x,int& k) {
  	k = 0;
  }
  int bfs() {
  	vis[0][0] = 1; // 从空罐子开始灌水 
  	que.push( node(0,0,0,"0") );
  	
  	while( !que.empty() ) {
  		node cur = que.front();
  		que.pop();
  
  		if (cur.a == x || cur.b == x) {
  			ans = cur.s;
  			return cur.step;
  		}
  
  		// 枚举6种操作
  		// 1.
  		int k = cur.a;
  		
  		fill(1,k);
  		if ( !vis[k][cur.b] ) {
  			vis[k][cur.b] = 1;
  			string nes = cur.s + '1';
  			node temp(k,cur.b,cur.step+1,nes);
  			que.push(temp);			
  		}
  
  		k = cur.b;
  		fill(2,k); 
  		if (!vis[cur.a][k]) {
  			vis[cur.a][k] = 1;
  			string nes = cur.s + '2';
  			node temp(cur.a,k,cur.step+1,nes);
  			que.push( temp );
  		}
  
  		k = cur.a;
  		if (k != 0) { // 已经为空,drop操作没有意义 
  			drop(1,k);
  			if (!vis[k][cur.b]) {
  				vis[k][cur.b] = 1;
  				string nes = cur.s + '3';
  				node temp(k,cur.b,cur.step+1,nes);
  				que.push( temp );	
  			}
  		}
  
  		k = cur.b;
  		if (k != 0) {
  			drop(2,k); 
  			if ( !vis[cur.a][k] ) {
  				vis[cur.a][k] = 1;
  				string nes = cur.s + '4';
  				node temp(cur.a,k,cur.step+1,nes);
  				que.push( temp );
  			}
  		}
  
  		int k1 = cur.a,k2 = cur.b;
  		pour(1,2,k1,k2); 
  		if ( !vis[k1][k2]) {
  			vis[k1][k2] = 1;
  			string nes = cur.s + '5';
  			node temp(k1,k2,cur.step+1,nes);
  			que.push( temp );
  		}
  
  		k1 = cur.a; k2 = cur.b;
  		pour(2,1,k2,k1);
  		if ( !vis[k1][k2]) {
  			vis[k1][k2] = 1;
  			string nes = cur.s + '6';
  			node temp(k1,k2,cur.step+1,nes);
  			que.push( temp );
  		}
  	}
  	return -1;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> liter[1] >> liter[2] >> x;
  	int flag = bfs();
  	if (flag == -1) {
  		printf("impossible\n");
  	} 
  	else {
  		printf("%d\n",flag);
  		for (int i=1; i<ans.length(); i++) {
  			if (ans[i] == '1') {
  				printf("FILL(1)\n");
  			} else if (ans[i] == '2') {
  				printf("FILL(2)\n");
  			} else if (ans[i] == '3') {
  				printf("DROP(1)\n");
  			} else if (ans[i] == '4') {
  				printf("DROP(2)\n");
  			} else if (ans[i] == '5') {
  				printf("POUR(1,2)\n");
  			} else if (ans[i] == '6') {
  				printf("POUR(2,1)\n");
  			}
  		}
  	}
  	return 0;
  }