当前位置:网站首页>poj 3414 Pots (bfs+线索)
poj 3414 Pots (bfs+线索)
2022-07-05 20:48:00 【全栈程序员站长】
大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
Pots
Time Limit: 1000MS | Memory Limit: 65536K | |||
---|---|---|---|---|
Total Submissions: 10071 | Accepted: 4237 | Special Judge |
Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
- FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
- DROP(i) empty the pot i to the drain;
- POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
思路:一共同拥有6种操作:把A中水倒掉,把A加满,把B里的水倒入A中。B和A类似。
罐子最大容积为100,设一个常量N=100, 开一个二维数组记录状态变化的值。
1、从水龙头往A里加水t,记录-t,
2、从水龙头往B里加水t,记录-t-N,
3、从B里面往A加水t,记录t
4、从A里面往B加水t。记录N+t
5、把A里水倒掉,记录2*N+t,(A原有水t)
6、把B里水倒掉,记录3*N+t,(B原有水t)
#include<stdio.h>
#include<queue>
#include<map>
#include<string>
#include<string.h>
using namespace std;
#define N 105
const int inf=0x1f1f1f1f;
int a,b,c,flag;
int mark[N][N];
struct node
{
int x,y,t;
friend bool operator<(node a,node b)
{
return a.t>b.t;
}
};
void prif(int x,int y) //递归输出路径
{
if(x==0&&y==0)
return ;
if(mark[x][y]>3*N)
{
prif(x,mark[x][y]-3*N);
printf("DROP(2)\n");
}
else if(mark[x][y]>2*N)
{
prif(mark[x][y]-2*N,y);
printf("DROP(1)\n");
}
else if(mark[x][y]>N)
{
int tmp=mark[x][y]-N;
prif(x+tmp,y-tmp);
printf("POUR(1,2)\n");
}
else if(mark[x][y]>0)
{
int tmp=mark[x][y];
prif(x-tmp,y+tmp);
printf("POUR(2,1)\n");
}
else if(mark[x][y]>-N)
{
int tmp=-mark[x][y];
prif(x-tmp,y);
printf("FILL(1)\n");
}
else if(mark[x][y]<-N)
{
int tmp=N+mark[x][y];
prif(x,y+tmp);
printf("FILL(2)\n");
}
}
void bfs()
{
priority_queue<node>q;
node cur,next;
mark[0][0]=inf; //该状态仅仅能出现一次。赋值为inf防止干扰其它值
mark[a][0]=-a;
mark[0][b]=-b-N;
cur.t=1;
cur.x=a;
cur.y=0;
q.push(cur);
cur.x=0;
cur.y=b;
q.push(cur);
while(!q.empty())
{
cur=q.top();
q.pop();
next.t=cur.t+1;
if(cur.x==c||cur.y==c)
{
flag=1;
printf("%d\n",cur.t);
prif(cur.x,cur.y);
return ;
}
if(cur.x<a) //向A加水
{
int tmp=a-cur.x;
next.y=cur.y;
next.x=a; //来自水龙头的水
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=-tmp;
q.push(next);
}
if(cur.y>0) //来自B的水
{
int tmp=min(cur.y,a-cur.x);
next.x=cur.x+tmp;
next.y=cur.y-tmp;
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=tmp;
q.push(next);
}
}
}
if(cur.y<b) //向B加水
{
int tmp=b-cur.y;
next.x=cur.x;
next.y=b; //来自水龙头的水
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=-tmp-N;
q.push(next);
}
if(cur.x>0) //来自A的水
{
int tmp=min(cur.x,b-cur.y);
next.y=cur.y+tmp;
next.x=cur.x-tmp;
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=tmp+N;
q.push(next);
}
}
}
if(cur.x>0) //倒掉水
{
int tmp=cur.x;
next.x=0;
next.y=cur.y;
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=2*N+tmp;
q.push(next);
}
}
if(cur.y>0)
{
int tmp=cur.y;
next.y=0;
next.x=cur.x;
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=3*N+tmp;
q.push(next);
}
}
}
}
int main()
{
while(scanf("%d%d%d",&a,&b,&c)!=-1)
{
memset(mark,0,sizeof(mark));
flag=0;
bfs();
if(!flag)
printf("impossible\n");
}
return 0;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117660.html原文链接:https://javaforall.cn
边栏推荐
- Norgen AAV提取剂盒说明书(含特色)
- How to form standard interface documents
- Point cloud file Dat file read save
- How to renew NPDP? Here comes the operation guide!
- Use of thread pool
- Is it safe to open an account online? Where can I get a low commission?
- 科普|英语不好对NPDP考试有影响吗 ?
- Which securities is better for securities account opening? Is online account opening safe?
- Research and development efficiency improvement practice of large insurance groups with 10000 + code base and 3000 + R & D personnel
- Leetcode (695) - the largest area of an island
猜你喜欢
Applet page navigation
实现浏览页面时校验用户是否已经完成登录的功能
培养机器人教育创造力的前沿科技
Welcome to the game and win rich bonuses: Code Golf Challenge officially launched
[quick start of Digital IC Verification] 2. Through an example of SOC project, understand the architecture of SOC and explore the design process of digital system
IC popular science article: those things about Eco
Frequent MySQL operations cause table locking problems
phpstudy小皮的mysql点击启动后迅速闪退,已解决
PHP反序列化+MD5碰撞
mysql全面解析json/数组
随机推荐
Abnova e (diii) (WNV) recombinant protein Chinese and English instructions
Abnova丨荧光染料 620-M 链霉亲和素方案
Leetcode (695) - the largest area of an island
Abnova maxpab mouse derived polyclonal antibody solution
Mathematical analysis_ Notes_ Chapter 9: curve integral and surface integral
Web Service简单入门示例
Selenium element information
2.8、项目管理过程基础知识
国外LEAD美国简称对照表
资源道具化
phpstudy小皮的mysql点击启动后迅速闪退,已解决
Duchefa细胞分裂素丨二氢玉米素 (DHZ)说明书
Duchefa low melting point agarose PPC Chinese and English instructions
台风来袭!建筑工地该如何防范台风!
获取前一天的js(时间戳转换)
Material Design组件 - 使用BottomSheet展现扩展内容(二)
挖财商学院给的证券账户安全吗?可以开户吗?
Make Jar, Not War
AI 从代码中自动生成注释文档
PHP反序列化+MD5碰撞