这几乎是一道超经典的智力题（emmmmmm可以这么说，当年面试还被亲身问过这问题）
题目描述
倒水问题 "fill A" 表示倒满A杯，"empty A"表示倒空A杯，"pour A B" 表示把A的水倒到B杯并且把B杯倒满或A倒空。
input：输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。
output：
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。
数据结构与思路
说到底这还是一道图论的题目，杯子里装载多少水就是几个不同的状态，需要判断的就是状态之间的转移，然后确定的找到一个转移的过程，实现从（0 ，0）到想要的状态。
恰巧刚刚写了另一个最短路径（记录路径）的问题 迷宫最短路的问题 思路是接近的。就干脆把思路也一起借鉴了过来。
对所有的状态转移都进行考虑（一共六种 1 倒空A 2. 倒空B 3. A倒入B/A被倒空了B不满 4. A倒入B/A未被倒空B满了 5. B倒入A/B被倒空了A不满 4. B倒入A/B未被倒空A满了）对全部六种状态进行判断，然后根据dfs的思路广度优先搜索所有的状态，同时记住自己的前置状态。其中有一个头疼的点就是怎么记住这个点已经被访问过了，我这里选取的办法是定义一个vis[][]数组，大小是两个杯子的两个容量（这样可以清楚的记录是否访问过该点but 会浪费空间，我觉得问题不大）。
搞清楚这一点，基本和迷宫探路思路相同
然后愉快的code 剩下的大致思路参考我的另一个博客迷宫最短路的问题
#include<queue>
#include<iostream>
using namespace std;
//六种变化， A倒空 A倒满 B倒空 B倒满 A倒B B倒A；
// 0代表起始
// 1 2 3 4 5 6
struct station
{
int tl;
int fillerA;
int fillerB; //当前状态的容量
int from; //回溯用的方式
int front; //
};
station ap[100000];
int vis[1000][1000];
void display(int k)
{
if(k==1){ cout<<"empty A"<<endl; }
else if(k==2){ cout<<"fill A"<<endl; }
else if(k==3){ cout<<"empty B"<<endl; }
else if(k==4){ cout<<"fill B"<<endl; }
else if(k==5){ cout<<"pour A B"<<endl; }
else if(k==6){ cout<<"pour B A"<<endl; }
}
int main()
{
int a,b,c;
cin>>a>>b>>c;
for (int i = 0; i < 1000; i++)
{
for (int j = 0; j < 1000; j++)
{
vis[i][j]=0;
}
}
queue<station> que;
station x;
x.tl=0;
x.fillerA=0;
x.fillerB=0;
x.from=0;
que.push(x);
ap[0]=x;
int j;
int i=1;
while(!que.empty())
{
station p=que.front();
que.pop();
if(p.fillerA==c||p.fillerB==c)
{
j=p.tl;
break;
}
//empty A
if(p.fillerA!=0&&!vis[0][p.fillerB])
{
station x1;
x1.fillerA=0;
x1.fillerB=p.fillerB;
x1.from=1;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[0][p.fillerB]=1;
que.push(x1);
i++;
}
//fill A
if(p.fillerA!=a&&!vis[a][p.fillerB])
{
station x1;
x1.fillerA=a;
x1.fillerB=p.fillerB;
x1.from=2;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[a][p.fillerB]=1;
que.push(x1);
i++;
}
//empty B
if(p.fillerB!=0&&!vis[p.fillerA][0])
{
station x1;
x1.fillerA=p.fillerA;
x1.fillerB=0;
x1.from=3;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[p.fillerA][0]=1;
que.push(x1);
i++;
}
//fill B
if(p.fillerB!=b&&!vis[p.fillerA][b])
{
station x1;
x1.fillerA=p.fillerA;
x1.fillerB=b;
x1.from=4;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[p.fillerA][b]=1;
que.push(x1);
i++;
}
//A 倒入B
//倒空A或者倒满B
//倒满B
if(p.fillerA>=(b-p.fillerB)&&!vis[p.fillerA-b+p.fillerB][b])
{
station x1;
x1.fillerA=p.fillerA+p.fillerB-b;
x1.fillerB=b;
x1.from=5;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[p.fillerA+p.fillerB-b][b]=1;
que.push(x1);
i++;
}
//倒空 A
if(p.fillerA<(b-p.fillerB)&&!vis[0][p.fillerA+p.fillerB])
{
station x1;
x1.fillerA=0;
x1.fillerB=p.fillerA+p.fillerB;
x1.from=5;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[0][p.fillerA+p.fillerB]=1;
que.push(x1);
i++;
}
//B 倒入A
//倒空B或者倒满A
//倒满A
if(p.fillerB>=(b-p.fillerA)&&!vis[a][p.fillerA+p.fillerB-a])
{
station x1;
x1.fillerA=a;
x1.fillerB=p.fillerA+p.fillerB-a;
x1.from=6;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[a][p.fillerA+p.fillerB-a]=1;
que.push(x1);
i++;
}
//倒空 B
if(p.fillerB<(b-p.fillerA)&&!vis[p.fillerA+p.fillerB][0])
{
station x1;
x1.fillerA=p.fillerA+p.fillerB;
x1.fillerB=0;
x1.from=6;
x1.front=p.tl;
x1.tl=i;
ap[i]=x1;
vis[p.fillerA+p.fillerB][0]=1;
que.push(x1);
i++;
}
}
station al[1000];
station p=ap[j];
int k=j;
int k1=0;
while(p.from!=0)
{
al[k1]=p;
p=ap[p.front];
k1++;
}
for(int t=k1;t>=0;t--)
{
display(al[t].from);
}
return 0;
}
网友评论