描述
给出三个水杯,大小不一,并且只有最大的水杯的水是装满的,其余两个为空杯子。三个水杯之间相互倒水,并且水杯没有标识,只能根据给出的水杯体积来计算。现在要求你写出一个程序,使其输出使初始状态到达目标状态的最少次数。
输入
第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行,第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 (体积小于等于相应水杯体积)表示我们需要的最终状态。
输出
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1。
样例输入
2
6 3 1
4 1 1
9 3 2
7 1 1
样例输出
3
-1
解题思路:bfs求最少的倒水次数,每次都有6种倒水可能,标记一下三个水杯的容量状态,用队列来模拟倒水过程,如果出现某个过程达到最终的倒水状态,则直接返回其倒水次数;否则直到队空,返回-1,说明不能到达最终的容量状态。详解看代码。
AC代码:
#include<bits/stdc++.h>
using namespace std;
int t,Vmax[],Est[],Cur[];
bool vis[][][];
struct node{int a,b,c,step;}cur,tmp;
queue<node> que;
int bfs(int x){
while(!que.empty())que.pop();
cur.a=x,cur.b=cur.c=cur.step=;
vis[cur.a][cur.b][cur.c]=true;
que.push(cur);
while(!que.empty()){
cur=que.front();que.pop();
if(cur.a==Est[]&&cur.b==Est[]&&cur.c==Est[])return cur.step;//到达最终的状态
for(int i=;i<;++i){
for(int j=;j<;++j){//6种倒水可能
tmp=cur;Cur[]=tmp.a,Cur[]=tmp.b,Cur[]=tmp.c;//每次重新赋值
if(i!=j&&Cur[i]>&&Cur[j]<Vmax[j]){//i-->j,如果第i个桶的水量大于0,并且第j个桶的水量不超过其最大容量
int gg=min(Cur[i],Vmax[j]-Cur[j]);//如果第j个桶剩余容量小于第i个桶里的水量,那么只能倒Vmax[j]-Cur[j];反之,将第i个桶的水量全部倒给第j个桶
Cur[i]-=gg,Cur[j]+=gg;// i--->j
if(!vis[Cur[]][Cur[]][Cur[]]){//状态未出现过
vis[Cur[]][Cur[]][Cur[]]=true;
tmp.a=Cur[],tmp.b=Cur[],tmp.c=Cur[];//重新赋值
tmp.step++;
que.push(tmp);
}
}
}
}
}
return -;//不满足条件则返回-1
}
int main(){
while(cin>>t){
while(t--){
for(int i=;i<;++i)cin>>Vmax[i];
for(int i=;i<;++i)cin>>Est[i];
memset(vis,false,sizeof(vis));
cout<<bfs(Vmax[])<<endl;
}
}
return ;
}