POJ 3414 Pots（bfs、简单但繁琐）

àì夳堔傛蜴生んèń 2022-12-05 15:11 42阅读 0赞

### POJ 3414 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. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

--------------------

Sample Input  
3 5 4

Sample Output  
6  
FILL(2)  
POUR(2,1)  
DROP(1)  
POUR(2,1)  
FILL(2)  
POUR(2,1)

--------------------

#### 题目大致思路： ####

枚举全部可能发生的情况，同时避免重复枚举。

#### 题目难点： ####

**如何表示每种情况最为合适？**  
答：创建结构，存储每种情况下，a，b 对应的容量和到达该情况所需要的操作数及路径。

//结构
    struct node{ 
    	int a, b;
    	int len;
    	int path[110];
    }Node, top;

值得注意是每种情况对应的路径，是通过一个整型数组表示的。  
该整型数组的每一个元素对应着每一个操作。**该题一共有6个操作**。

//操作
    string cz[6] = { 
    	"FILL(1)",
    	"FILL(2)",
    	"DROP(1)",
    	"DROP(2)",
    	"POUR(1,2)",
    	"POUR(2,1)"
    };

--------------------

将每种可能枚举到的情况弄清楚后，题目就变得清晰起来。

实现代码

#include<iostream>
    #include<memory.h>
    #include<string>
    #include<queue>
    using namespace std;
    
    int A, B, C;
    bool judge[110][110];
    
    struct node{ 
    	int a, b;
    	int len;
    	int path[110];
    }Node, top;
    
    string cz[6] = { 
    	"FILL(1)",
    	"FILL(2)",
    	"DROP(1)",
    	"DROP(2)",
    	"POUR(1,2)",
    	"POUR(2,1)"
    };
    
    void putout(node x){ 
    	cout<<x.len<<endl;
    	for(int i=0; i<x.len; i++)
    		cout<<cz[x.path[i]]<<endl;
    		
    	return; 
    }
    
    void bfs(){ 
    	memset(judge, false, sizeof(judge));
    	memset(Node.path, 0, sizeof(Node.path));
    	Node.a = 0;
    	Node.b = 0;
    	Node.len = 0;
    	queue <node> q;
    	q.push(Node);
    	judge[0][0]=true;
    	
    	while(!q.empty()){ 
    		top = q.front();
    		q.pop();
    		
    		//输出结果 
    		if(top.a==C||top.b==C){ 
    			putout(top);
    			return;
    		}
    		
    		//路径 
    		Node = top;
    		Node.len++;
    		
    		//FILL(a)
    		Node.a = A;
    		Node.b = top.b;
    		Node.path[top.len] = 0;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b]=true;
    			q.push(Node);
    		}
    		
    		//FILL(b)
    		Node.a = top.a;
    		Node.b = B;
    		Node.path[top.len] = 1;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b]=true;
    			q.push(Node);
    		}
    	
    		//DROP(a)
    		Node.a = 0;
    		Node.b = top.b;
    		Node.path[top.len] = 2;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b]=true;
    			q.push(Node);
    		}
    		
    		//DROP(b)
    		Node.a = top.a;
    		Node.b = 0;
    		Node.path[top.len] = 3;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b]=true;
    			q.push(Node);
    		}
    	
    		//POUR(a, b)
    		if(top.a+top.b>B){ 
    			Node.a = top.a+top.b-B;
    			Node.b = B;
    		}
    		else{ 
    			Node.a = 0;
    			Node.b = top.a+top.b;
    		}
    		Node.path[top.len] = 4;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b] = true;
    			q.push(Node);
    		}
    		
    		//POUR(b, a)
    		if(top.a+top.b>A){ 
    			Node.a = A;
    			Node.b = top.a+top.b-A;
    		}
    		else{ 
    			Node.a = top.a+top.b;
    			Node.b = 0;
    		}
    		Node.path[top.len] = 5;
    		if(!judge[Node.a][Node.b]){ 
    			judge[Node.a][Node.b] = true;
    			q.push(Node);
    		}
    	}
    	cout<<"impossible"<<endl;
    	
    	return;
    }
    
    int main(){ 
    	cin>>A>>B>>C;
    	bfs();
    	return 0;
    }