POJ - 3414 Pots BFS(著名倒水问题升级版)
Pots
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 jis 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) 题意:倒水问题。给你两个标有容量的空杯子,求最少需要多少步能够倒出含指定容量的水。并输出倒水步骤(升级版)。
思路:看到最少步数和输出具体步骤就应该想到BFS。用二维数组b来记录两个杯子的容量。分六步,倒满1、倒满2、倒空1、倒空2、1倒入2、2倒入1。倒入水时要保证不会溢出,所以倒入要分全部倒入和部分倒入两种情况。步骤较多,所以代码啰嗦些。。
#include<stdio.h>
#include<queue>
using namespace std; int b[][],re[];
struct Node{
int x,y,s,c,f,d;
}node[]; int main()
{
int x,y,z,c,f,i;
queue<Node> q;
scanf("%d%d%d",&x,&y,&z);
if(z==) printf("0\n"); //一定注意。。
else{
b[][]=;
node[].x=;
node[].y=;
node[].s=;
node[].c=;
node[].f=;
node[].d=;
q.push(node[]);
c=;f=;
while(q.size()){
for(i=;i<=;i++){
if(i==&&q.front().x<x&&b[x][q.front().y]==){
b[x][q.front().y]=;
node[++c].x=x;
node[c].y=q.front().y;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
else if(i==&&q.front().y<y&&b[q.front().x][y]==){
b[q.front().x][y]=;
node[++c].x=q.front().x;
node[c].y=y;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
else if(i==&&q.front().x>&&b[][q.front().y]==){
b[][q.front().y]=;
node[++c].x=;
node[c].y=q.front().y;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
else if(i==&&q.front().y>&&b[q.front().x][]==){
b[q.front().x][]=;
node[++c].x=q.front().x;
node[c].y=;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
else if(i==&&q.front().x>&&q.front().y<y){
int tx=q.front().x<y-q.front().y?:q.front().x+q.front().y-y;
int ty=q.front().x<y-q.front().y?q.front().x+q.front().y:y;
if(b[tx][ty]==){
b[tx][ty]=;
node[++c].x=tx;
node[c].y=ty;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
}
else if(i==&&q.front().x<x&&q.front().y>){
int tx=x-q.front().x<q.front().y?x:q.front().x+q.front().y;
int ty=x-q.front().x<q.front().y?q.front().x+q.front().y-x:;
if(b[tx][ty]==){
b[tx][ty]=;
node[++c].x=tx;
node[c].y=ty;
node[c].s=q.front().s+;
node[c].c=c;
node[c].f=q.front().c;
node[c].d=;
if(node[c].x==z||node[c].y==z){
f=node[c].s;
break;
}
q.push(node[c]);
}
}
}
if(f!=) break;
q.pop();
}
if(f==) printf("impossible\n");
else{
printf("%d\n",f);
for(i=;i<=f;i++){
re[i]=node[c].d;
c=node[c].f;
}
for(i=f;i>=;i--){
if(re[i]==) printf("FILL(1)\n");
else if(re[i]==) printf("FILL(2)\n");
else if(re[i]==) printf("DROP(1)\n");
else if(re[i]==) printf("DROP(2)\n");
else if(re[i]==) printf("POUR(1,2)\n");
else if(re[i]==) printf("POUR(2,1)\n");
}
}
}
return ;
}
最新文章
- ios小数向上、下取整,计算结果向上、下取整
- RFID工作流程
- Delphi Webbrowser 修改 textarea 值 百度
- Impossible to load an image in xcassets on bundle
- 关于Delphi中多线程传递参数的简单问题
- HEU KMS Activator v11.1.0 Windows激活
- 17.4---返回max,不用if
- [tp3.2.1]查询(2)
- [Python] 中文编码问题:raw_input输入、文件读取、变量比较等str、unicode、utf-8转换问题
- 查找文件并执行的shell命令
- java虚拟机(一)——内存管理机制与OOM异常
- 剑指Offer:面试题18——树的子结构(java实现)
- C# 汉子增加UTF-8头
- flume 自己定义 hbase sink 类
- ssh爆破脚本
- zip 安装mysql 和遇到的坑
- java的优势解读
- python爬虫爬取京东、淘宝、苏宁上华为P20购买评论
- 【Linux】Centos配置ssh无密码登录
- linux基本格式和常用目录命令一