当前位置:网站首页>POJ 3414 pots (bfs+ clues)
POJ 3414 pots (bfs+ clues)
2022-07-05 20:52:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .
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)
Ideas : We all have 6 Kind of operation : hold A The water is poured out , hold A Fill it up with , hold B Pour the water in A in .B and A similar .
The maximum volume of the tank is 100, Set a constant N=100, Open a two-dimensional array to record the value of state change .
1、 From the tap to A Add water in t, Record -t,
2、 From the tap to B Add water in t, Record -t-N,
3、 from B Inside A Add water t, Record t
4、 from A Inside B Add water t. Record N+t
5、 hold A Pour out the water , Record 2*N+t,(A Original water t)
6、 hold B Pour out the water , Record 3*N+t,(B Original water 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) // Recursive output path
{
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; // This state can only appear once . The assignment is inf Prevent interference with other values
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) // towards A Add water
{
int tmp=a-cur.x;
next.y=cur.y;
next.x=a; // Water from the tap
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=-tmp;
q.push(next);
}
if(cur.y>0) // come from B Of water
{
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) // towards B Add water
{
int tmp=b-cur.y;
next.x=cur.x;
next.y=b; // Water from the tap
if(!mark[next.x][next.y])
{
mark[next.x][next.y]=-tmp-N;
q.push(next);
}
if(cur.x>0) // come from A Of water
{
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) // Pour out the water
{
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;
}
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/117660.html Link to the original text :https://javaforall.cn
边栏推荐
- Wanglaoji pharmaceutical's public welfare activity of "caring for the most lovely people under the scorching sun" was launched in Nanjing
- ClickHouse 复制粘贴多行sql语句报错
- 珍爱网微服务底层框架演进从开源组件封装到自研
- 清除app data以及获取图标
- How to make ERP inventory accounts of chemical enterprises more accurate
- Make Jar, Not War
- 国外LEAD美国简称对照表
- Abnova丨DNA 标记高质量控制测试方案
- The Chinese Academy of Management Sciences gathered industry experts, and Fu Qiang won the title of "top ten youth" of think tank experts
- Prosci LAG-3 recombinant protein specification
猜你喜欢
随机推荐
Specification of protein quantitative kit for abbkine BCA method
教你自己训练的pytorch模型转caffe(一)
Écrire une interface basée sur flask
mysql全面解析json/数组
Norgen AAV提取剂盒说明书(含特色)
Duchefa cytokinin dihydrozeatin (DHZ) instructions
How to renew NPDP? Here comes the operation guide!
Chemical properties and application instructions of prosci Lag3 antibody
如何让化工企业的ERP库存账目更准确
IC popular science article: those things about Eco
序列联配Sequence Alignment
MySQL fully parses json/ arrays
shell编程100例
ODPS 下一个map / reduce 准备
清除app data以及获取图标
Analysis of steam education mode under the integration of five Education
Interpreting the daily application functions of cooperative robots
3.3 project evaluation
AI automatically generates annotation documents from code
Abnova DNA marker high quality control test program