状态搜索。类似八数码问题
AC代码
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=200+5; int vis[maxn][maxn];//是否访问过该节点 struct node { int fill[3]; //当前状态的水的分布 int dist; //当前状态倒水量 bool operator < (const node &p) const //排序 { return dist>p.dist; } }; int ans[maxn],cup[3]; void update_ans(node &u) //细节处理 难点 { for(int i=0;i<3;++i) { int d=u.fill[i]; if(ans[d]<0||u.dist<ans[d]) ans[d]=u.dist; } } void bfs(int a,int b,int c,int d) { cup[0]=a,cup[1]=b,cup[2]=c; node start; start.fill[0]=0,start.fill[1]=0,start.fill[2]=c; start.dist=0; priority_queue<node>q; q.push(start); while(!q.empty()) { node u=q.top(); q.pop(); update_ans(u); if(ans[d]>=0) break; //尝试从第i个杯子中向第j个倒水 for(int i=0;i<3;++i) for(int j=0;j<3;++j) { if(i==j) continue; if(u.fill[i]==0||u.fill[j]==cup[j]) continue; int pour=min(u.fill[i],cup[j]-u.fill[j]); node temp; memcpy(&temp,&u,sizeof(u)); temp.dist=u.dist+pour; temp.fill[i]-=pour; temp.fill[j]+=pour; if(!vis[temp.fill[0]][temp.fill[1]]) { q.push(temp); vis[temp.fill[0]][temp.fill[1]]=1; } } } while(d>=0) { if(ans[d]>=0) { printf("%d %d\n",ans[d],d); return ; } --d; } } int main() { int T,a,b,c,d; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&a,&b,&c,&d); memset(ans,-1,sizeof(ans)); memset(vis,0,sizeof(vis)); bfs(a,b,c,d); } return 0; }如有不当之处欢迎指出！
