路径搜索问题，用bfs可以解决
这里用来一个二维数组visit进行判重。
因为如果搜索到了相同的状态那么第一个水杯中的水量x1和第二个水杯中的水量x2将会相同，所以可以通过visit[x1][x2] = 1判断这个状态事先被访问过，无需插入队列中
注意这里是要找倒水量最少的解，不是总的步数最少，所以要用优先队列，到水量少的先出队，所以需要操作符重载了
#include<iostream> #include <queue> #include <string.h> using namespace std; const int maxn = 200+5; struct State { int x[4],total; bool operator < (const State& rhs) const { return total > rhs.total; } }; int visit[maxn][maxn]; int liter[4],d,d1;//d1记录当前最接近d且小于d的值 State goal;//记录找到的状态 int from[] = {1,1,2,2,3,3}; int to[] = {2,3,1,3,1,2}; State pour(State s, int f, int t) { if(s.x[f] >= liter[t] - s.x[t]) { s.total += liter[t] -s.x[t]; s.x[f] -= liter[t] - s.x[t]; s.x[t] = liter[t]; } else { s.total += s.x[f]; s.x[t] += s.x[f]; s.x[f] = 0; } return s; } void bfs() { d1 = -1; priority_queue<State> qu; State sbegin; sbegin.x[1] = 0;sbegin.x[2] = 0; sbegin.x[3] = liter[3]; sbegin.total = 0; visit[sbegin.x[1]][sbegin.x[2]] = 1; qu.push(sbegin); while(!qu.empty()) { State s = qu.top();qu.pop(); if(s.x[1] == d || s.x[2] ==d || s.x[3] ==d) { goal = s; d1 = d; return; } for(int i = 1; i<= 3; i++) { if(s.x[i] > d1 && s.x[i] < d) { d1 = s.x[i]; goal = s; } } for(int i = 0; i < 6; i++) { State nexts = pour(s,from[i], to[i]); if(!visit[nexts.x[1]][nexts.x[2]] ) { visit[nexts.x[1]][nexts.x[2]] = 1; qu.push(nexts); } } } } int main() { int T; cin>>T; while(T--) { //初始化 memset(visit,0,sizeof(visit)); cin>>liter[1]>>liter[2]>>liter[3]>>d; bfs(); cout<<goal.total<<" "<<d1<<endl; } return 0; }
