TOJ 2778 数据结构练习题――分油问题(广搜和哈希)

描述

设有大小不等的三个无刻度的油桶，分别能盛满x，y，z公升油。初始时，第一个油桶盛满油，第二、三个油桶为空，在某一个油桶上分出targ公升油。

输入

输入包含多组测试数据。每组数据包含一行。分别x，y，z，targ四个整数，x，y，z，targ都大于等于0，且小于32767。

输出

对应每组输出YES或者NO。如果可以分出targ公升油就输出YES，否则就输出NO。

样例输入

80 50 30 40

样例输出

YES

提示

使用队列。分油过程中，由于油桶上没有刻度，只能将油桶倒满或者倒空。三个油桶盛油的总量始终等于初始时第一个油桶盛满的油量。

题意

给你3个油桶，初始化第一个装满，第二个第三个为空，求能否有一个桶为targ升油，不能有丢弃

题解

一开始没读懂题意，傻逼了半天，题目读懂后就很easy了

这里用广搜搜索所有情况就行了，很暴力很无脑

这里由于X,Y,Z有点大，存状态开三维数组爆内存，这里用了map中的哈希思想

代码

 #include<bits/stdc++.h>

 using namespace std;

 struct Node

 {

     int x,y,z;

     Node(int x,int y,int z):x(x),y(y),z(z){}

 };

 string To_string(int x,int y,int z)

 {

     stringstream ss;

     ss<<x;ss<<y;ss<<z;

     return ss.str();

 }

 int main()

 {

     int x,y,z,targ;

     while(scanf("%d%d%d%d",&x,&y,&z,&targ)!=EOF)

     {

         int flag=;

         queue<Node> q;

         map<string,int> ma;

         q.push(Node(x,,));

         while(!q.empty())

         {

             Node h=q.front();q.pop();

             if(h.x==targ||h.y==targ||h.z==targ){flag=;break;}//成功

             if(ma[To_string(h.x,h.y,h.z)])continue;//状态有过，跳过

             ma[To_string(h.x,h.y,h.z)]=;//标记

             if(h.x+h.y<=y)q.push(Node(,h.x+h.y,h.z));//x->y不会溢出，全倒过去

             else q.push(Node(h.x-y+h.y,y,h.z));//x->y会溢出，y倒满

             if(h.x+h.z<=z)q.push(Node(,h.y,h.x+h.z));//x->z

             else q.push(Node(h.x-z+h.z,y,z));

             if(h.x+h.y<=x)q.push(Node(h.x+h.y,,h.z));//y->x

             else q.push(Node(x,h.y-x+h.x,h.z));

             if(h.y+h.z<=z)q.push(Node(h.x,,h.y+h.z));//y->z

             else q.push(Node(h.x,h.y-z+h.z,z));

             if(h.x+h.z<=x)q.push(Node(h.x+h.z,h.y,));//z->x

             else q.push(Node(x,h.y,h.z-x+h.x));

             if(h.y+h.z<=y)q.push(Node(x,h.y+h.z,));//z->y

             else q.push(Node(h.x,y,h.z-y+h.y));

         }

         printf("%s\n",flag?"YES":"NO");

     }

     return ;

 }

巴特西

TOJ 2778 数据结构练习题――分油问题(广搜和哈希)

最新文章

热门文章