当前位置:网站首页>Poj3414 extensive search
Poj3414 extensive search
2022-07-05 21:43:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
<span style="color:#330099;">/*
D - D
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
POJ 3414
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)
By Grant Yuan
2014.7.14
poj 3414
Guang Shu
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
bool flag=0;
int next[6]={0,1,2,3,4,5};
int a,b,c;
int aa,bb,cc;
typedef struct{
int a;
int b;
int f;
int sum;
int ope;
}node;
int res;
node q[10000];
bool mark[101][101];
int top,base;
int top1;
int s[10000];
bool can(int x1,int y1)
{
if(x1>=0&&x1<=aa&&y1>=0&&y1<=bb&&mark[x1][y1]==0)
return 1;
return 0;
}
void slove()
{ int a1,b1,f1,a2,b2;
while(top>=base){//cout<<"zhang"<<endl;
if(q[base].a==cc||q[base].b==cc){
flag=1;
res=q[base].sum;
break;
}
for(int i=0;i<6;i++){
if(i==0)
{ a1=aa;
b1=q[base].b;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;}
}
else if(i==1)
{
a1=q[base].a;
b1=bb;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;}
}
else if(i==2)//1dao2
{ int m,n;
m=q[base].a;
n=bb-q[base].b;
if(m>=n){
a1=m-n;
b1=bb;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;} }
else{
a1=0;
b1=m+q[base].b;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;}
}}
else if(i==3)//1dao2
{ int m,n;
m=aa-q[base].a;
n=q[base].b;
if(n>=m){
a1=aa;
b1=n-m;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;} }
else{
b1=0;
a1=n+q[base].a;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;}
}}
else if(i==4)
{
a1=0;
b1=q[base].b;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;
}}
else if(i==5)
{
b1=0;
a1=q[base].a;
if(can(a1,b1)){
q[++top].a=a1;
q[top].b=b1;
q[top].f=base;
q[top].sum=q[base].sum+1;
q[top].ope=i;
mark[a1][b1]=1;
}
}
}
base++;
}}
void print()
{ top1=-1;
int i=base,j;
while(1){
s[++top1]=q[i].ope;
j=q[i].f;
i=j;
if(i==0)
break;
}
for(j=top1;j>=0;j--)
{
if(s[j]==0)
cout<<"FILL(1)"<<endl;
else
if(s[j]==1)
cout<<"FILL(2)"<<endl;
else
if(s[j]==2)
cout<<"POUR(1,2)"<<endl;
else
if(s[j]==3)
cout<<"POUR(2,1)"<<endl;
else
if(s[j]==4)
cout<<"DROP(1)"<<endl;
else
if(s[j]==5)
cout<<"DROP(2)"<<endl;
}
}
int main()
{
cin>>aa>>bb>>cc;
top=-1;
memset(mark,0,sizeof(mark));
mark[0][0]=1;
base=0;
q[++top].a=0;
q[top].b=0;
q[top].f=0;
q[top].sum=0;
q[top].ope=0;
slove();
if(flag==0) cout<<"impossible"<<endl;
else{cout<<res<<endl;
print();}
return 0;
}
</span>
Copyright notice : This article is an original blog article . Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117579.html Link to the original text :https://javaforall.cn
边栏推荐
- 1.2 download and installation of the help software rstudio
- 华为云ModelArts文本分类–外卖评论
- 基于 Ingress Controller 在集群外访问 Zadig 自测环境(最佳实践)
- R language [data management]
- 怎么利用Tensorflow2进行猫狗分类识别
- 使用Aspect制作全局异常处理类
- oracle 控制文件的多路复用
- Reading and writing operations of easyexcel
- Huawei fast game failed to call the login interface, and returned error code -1
- Clickhouse copy paste multi line SQL statement error
猜你喜欢
Longest swing sequence [greedy practice]
Deeply convinced plan X - network protocol basic DNS
Li Kou ----- the maximum profit of operating Ferris wheel
Uni app Bluetooth communication
"Grain mall" -- Summary and induction
Summarize the reasons for 2XX, 3xx, 4xx, 5xx status codes
ICMP 介绍
校招期间 准备面试算法岗位 该怎么做?
Parker驱动器维修COMPAX控制器维修CPX0200H
EBS Oracle 11g 克隆步骤(单节点)
随机推荐
Selenium gets the verification code image in DOM
Analysis and test of ModbusRTU communication protocol
秋招将临 如何准备算法面试、回答算法面试题
递归查询多级菜单数据
postgis 安装地理信息扩展
Some things make feelings nowhere to put
Xlrd common operations
力扣------经营摩天轮的最大利润
HDU 4391 Paint The Wall 段树(水
one hundred and twenty-three thousand four hundred and fifty-six
EBS Oracle 11g 克隆步骤(单节点)
他们主动布局(autolayout)环境的图像编辑器
Recursive query of multi-level menu data
selenium 获取dom内属性值的方法
初级软件测试必问面试题
The solution to the problem that Oracle hugepages are not used, causing the server to be too laggy
2.2.3 output of documents
MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
资深电感厂家告诉你电感什么情况会有噪音电感噪音是比较常见的一种电感故障情况,如果使用的电感出现了噪音大家也不用着急,只需要准确查找分析出什么何原因,其实还是有具体的方法来解决的。作为一家拥有18年品牌