当前位置:网站首页>Poj3414广泛搜索
Poj3414广泛搜索
2022-07-05 21:40:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
<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
广搜
*/
#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>
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117579.html原文链接:https://javaforall.cn
边栏推荐
- Vant source code parsing event Detailed explanation of TS event processing global function addeventlistener
- Three components of openpyxl
- How to send samples when applying for BS 476-7 display? Is it the same as the display??
- 【日常训练--腾讯精选50】89. 格雷编码(看题解才会的)
- 办公遇到的问题--
- Oracle检查点队列–实例崩溃恢复原理剖析
- Golang(1)|从环境准备到快速上手
- Some things make feelings nowhere to put
- leetcode:1755. Sum of subsequences closest to the target value
- Get JS of the previous day (timestamp conversion)
猜你喜欢
Oracle检查点队列–实例崩溃恢复原理剖析
MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
Deployment of Jenkins under win7
Xlrd common operations
Realize the function of verifying whether the user has completed login when browsing the page
Exercise 1 simple training of R language drawing
R language learning notes
PIP install beatifulsoup4 installation failed
Yolov5 training custom data set (pycharm ultra detailed version)
Teach yourself to train pytorch model to Caffe (III)
随机推荐
Li Kou ----- the maximum profit of operating Ferris wheel
Simple interest mode - lazy type
Two ways to realize video recording based on avfoundation
LeetCode_ Hash table_ Difficulties_ 149. Maximum number of points on the line
Selenium gets the verification code image in DOM
Access Zadig self-test environment outside the cluster based on ingress controller (best practice)
2.2 basic grammar of R language
Making global exception handling classes with aspect
Realize the function of verifying whether the user has completed login when browsing the page
Pointer parameter passing vs reference parameter passing vs value parameter passing
PostGIS installation geographic information extension
Oracle HugePages没有被使用导致服务器很卡的解决方法
Deep merge object deep copy of vant source code parsing
Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
JS common method encapsulation
MySQL InnoDB Architecture Principle
力扣------经营摩天轮的最大利润
Uni app Bluetooth communication
PIP install beatifulsoup4 installation failed
854. 相似度为 K 的字符串 BFS