Pots
Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
1.FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
2.DROP(i) empty the pot i to the drain;
3.POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation.
Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
Source
Northeastern Europe 2002, Western Subregion
题意:倒水 6种操作。各自是1:向1杯装满水。2:向2杯装满水。3:1杯水倒入2杯。4:2杯水倒入1杯。5:1杯水倒出;6:2杯水倒出 思路:简单BFS+回溯 广搜时借用节点下标。记录父亲节点,同一时候记录操作相应的数字,以及终点节点 从终点节点回溯,打印路径 #include <cstdio> #include <queue> #include <cstring> #include <cstdlib> #include <vector> using namespace std ; int a , b , c ; int num , flag ; //num 记录搜索步数 , flag 记录终点搜索步数 int ans[101][101] ; //记录步数 struct next { int op ; //操作 int par ; //父亲 } nn[10001] ; void dfs( int flag ) { //深搜打印路径 if( flag > 0 ) { dfs(nn[flag].par) ;} if(nn[flag].op == 1 ) cout << "FILL(1)" << endl; else if(nn[flag].op == 2 ) cout << "FILL(2)" << endl; else if(nn[flag].op == 3 ) cout << "POUR(1,2)" << endl; else if(nn[flag].op == 4 ) cout << "POUR(2,1)" << endl; else if(nn[flag].op == 5 ) cout << "DROP(1)" << endl; else if(nn[flag].op == 6 ) cout << "DROP(2)" << endl; } bool bfs() { memset(ans, 0 ,sizeof(ans)) ; ans[0][0] = 1; queue<int> A ; queue<int> B ; while(!A.empty()||!B.empty() ) { A.pop() ;B.pop() ; } A.push(0) ; B.push(0) ; int time = 0 , tempa , tempb ; //time 当前节点数 while(!A.empty()) { int inita = A.front () ; int initb = B.front() ; A.pop() ;B.pop() ; //FILL(1) tempa = a ; tempb = initb ; if ( !ans[tempa][tempb] ) { //保证未訪问过 A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1 ; nn[num].op = 1 ; nn[num++].par = time ; //记录父亲节点 if ( tempa==c || tempb==c ) { flag = num-1 ; //记录终点节点 break; } } //FILL(2) tempa = inita ; tempb = b ; if( !ans[tempa][tempb] ) { A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1; nn[num].op = 2 ; nn[num++].par = time ; if(tempa==c||tempb==c) { flag = num -1; break ; } } //POUR(1,2) if(inita <= b-initb) tempa = 0 ; //倒完 else tempa = inita - ( b - initb) ;//倒部分 tempb = (initb + inita) ; if(tempb> b) tempb = b ; //小心溢出 if( !ans[tempa][tempb] ) { A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1; nn[num].op = 3 ; nn[num++].par = time ; if(tempa==c||tempb==c) { flag = num-1 ; break ; } } //POUR(2,1) if(initb <= a-inita) tempb = 0 ; else tempb = initb - ( a - inita) ; tempa = (initb + inita) ; if(tempa> a) tempa = a ; if( !ans[tempa][tempb] ) { A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1; nn[num].op = 4 ; nn[num++].par = time ; if(tempa==c||tempb==c) { flag = num-1 ; break ; } } //DROP(1) tempa = 0 ; tempb = initb ; if( !ans[tempa][tempb] ) { A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1; nn[num].op =5 ; nn[num++].par = time ; if(tempa==c||tempb==c) { flag = num-1 ; break; } } //DROP(2) tempb = 0 ; tempa = inita ; if( !ans[tempa][tempb] ) { A.push(tempa) ; B.push(tempb) ; ans[tempa][tempb] = ans[inita][initb] +1; nn[num].op = 6 ; nn[num++].par = time ; if(tempa==c||tempb==c) { flag = num-1 ; break; } } ++time ; //记录节点数 } if( flag ) { printf("%d ",max(ans[tempa][tempb],ans[tempb][tempa])-1) ;//ans[0][0] = 1 , 故减之 dfs(flag) ; return true ; } return false ; } int main( ) { while(~scanf("%d %d %d",&a,&b,&c) ) { num = 1 ; flag = 0; if(!bfs()) cout << "impossible" << endl ; } return 0 ; }