韩信走马分油c++

题目

• 把油桶里还剩下的10斤油平分，只有一个能装3斤的油葫芦和一个能装7斤的瓦罐。如何分。

算法

1. 油壶编号0，1，2。不同倒法有：把油从0倒进0（本壶到本壶，无效），从0倒进1，从0倒进2；从1倒进0，从1倒进1（无效），从1倒进2；从2倒进0，从2倒进1，从2倒进2（无效）。此过程可用二个for循环来摸拟，见下图。
2. 为方便计算，以这种倒法为一次大循环，然后再不停地重复倒油。每次倒油，3个壶中的油量：10，0，0（举个例）是确定值，存入向量vector中。
3. 每种结果，再重复1中的9种倒法，又会产生更多的油量结果vector[0]、vector[1]、vector[2]。结果产生更多的结果……
4. 符合广度优先算法。用双端队列存储每一种结果，把初始值（10，0，0）入队。取出进行处理（相互之间倒油，有9种可能），将结果入队。再出队，处理，再入队，直到队列为空。
5. 倒油的结果（10，0，0），其种类是有限的，不同的倒油方法会产生重复结果现象，用map来去重。而且map还可以记录油的变化过程，即map[vector₀]=vector₀是初始，以后产生一个新结果作为键，值为上一次的状态。
   

代码

#include<iostream>
#include<vector>
#include<map>
#include<deque>
using namespace std;
//判断油壶的状态是否符合结果，即有没有出现5l油量的壶 
bool ok(vector<int>& v,int goal){
	for(int n:v){
		if(n==goal) return true;
	}
	return false;
}
//广度优先算法 
bool f(int* a,vector<int> v,int goal){
	deque<vector<int> > q;//双端队列 
	q.push_back(v);//初始值入队 
	map<vector<int>,vector<int> >  m;
	m[v]=v;
	while(1){
		int n=q.size();
		if(n==0) return false;
		for(int i=0;i<n;i++){
			vector<int> t=q.front();
			if(ok(t,goal)){
				while(m[t]!=t){
					cout<< t[0] <<"-"<< t[1]<< "-"<<t[2]<<endl;
					t=m[t];
				}
				return true;
			} 
			q.pop_front();
			//倒油，从i壶倒进j壶 
			for(int i=0;i<3;++i)
				for(int j=0;j<3;++j){
					if(i==j) continue;
					if(t[i]==0) continue;
					if(t[j]==a[j]) continue;
					vector<int> t1=t;
					t1[j]+= t1[i];
					t1[i]=0;
					if(t1[j]>a[j]){//接收的油超过其容量 
						t1[i]=t1[j]-a[j];
						t1[j]=a[j];
					}
					if(m.count(t1)) continue;
					m[t1]=t;
					q.push_back(t1);
				} 
		}
	}
}
int main(){
	int a[]={10,7,3};
	vector<int> v={10,0,0};
	f(a,v,5);
	return 0;
}