2 6 3 1 4 1 1 9 3 2 7 1 1
3 -1
记得一年前看这道题 感觉说的是什么啊 完全看不懂 没有想法
前天有时间再看看 想用dfs做了 可是做的过程中发现了许多问题 以至于我没有做出来
看到评论区有人用bfs做 就用bfs了
#include <stdio.h> #include <queue> #include <string.h> using namespace std; struct node { int step; int state[3]; friend bool operator<(node x,node y) { return x.step>y.step; } }; //当前三个水杯的状态 int curState[3]; //三个水杯目标状态 int endState[3]; //三个水杯的最大容量 int maxState[3]; bool vis[101][101][101]; //i向j倒水 void pourWater(int i,int j) { //如果j水杯是满的 或者 i水杯没水 返回 if(curState[j]==maxState[j]||curState[i]==0) return ; //如果i水杯当前的水容量大于j水杯空着的容量 if(curState[i]>=maxState[j]-curState[j]) { curState[i]=curState[i]-(maxState[j]-curState[j]); curState[j]=maxState[j]; } //如果i水杯当前的水容量小于水杯空着的容量 else { curState[j]+=curState[i]; curState[i]=0; } } int bfs() { priority_queue<node>s; while(!s.empty()) s.pop(); node temp,temp1; temp.state[0]=maxState[0]; temp.state[1]=temp.state[2]=temp.step=0; vis[maxState[0]][0][0]=true; s.push(temp); while(!s.empty()) { temp=temp1=s.top(); s.pop(); if(temp.state[0]==endState[0]&&temp.state[1]==endState[1]&&temp.state[2]==endState[2]) return temp.step; curState[0]=temp.state[0]; curState[1]=temp.state[1]; curState[2]=temp.state[2]; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(i!=j&&curState[i]!=0&&curState[j]!=maxState[j]) { pourWater(i,j); temp.state[0]=curState[0]; temp.state[1]=curState[1]; temp.state[2]=curState[2]; temp.step++; if(!vis[curState[0]][curState[1]][curState[2]]) { vis[curState[0]][curState[1]][curState[2]]=true; s.push(temp); } temp=temp1; curState[0]=temp.state[0]; curState[1]=temp.state[1]; curState[2]=temp.state[2]; } } } } return -1; } int main() { int ncase; scanf("%d",&ncase); while(ncase--) { memset(vis,false,sizeof(vis)); scanf("%d %d %d",&maxState[0],&maxState[1],&maxState[2]); scanf("%d %d %d",&endState[0],&endState[1],&endState[2]); printf("%d\n",bfs()); } }
原文:http://blog.csdn.net/su20145104009/article/details/50929717