Pots
题意：
给定两个容量分别为 A升 和 B 升的罐子。可以执行以下操作：
1、FILL(i) —— 从水龙头引水把 i 罐注满（1≤i≤2）；
2、DROP(i) —— 倒空 i 罐到排水管；
3、POUR(i，j) —— 把 i 罐的水倒入 j 罐；操作后，要么 j 罐满了（ i 罐中可能还剩下一些水），要么 i 罐空了（所有水都倒入 j 罐中）。
编写一个程序，找出这些操作中最短的可能顺序，使得其中一个容器中产生C升的水。
输出最少的操作数 K 并按顺序输出 K 行操作，若无法按要求得到结果，则输出“impossible”。
数据范围：
1<=A，B<=100，C≤max(A,B).
解题思路：
宽度优先搜素
具体的思路是 通过结构体数组来记录每次执行操作后的状态，并把每次操作后符合条件的状态入队，当队列不为空时取出最前面的状态继续加以判断，若已得到结果，则结束 bfs 并输出操作数以及具体的操作步骤，若队列为空仍未能得到结果，则输出“impossible”。
其中的难点大概就在于如何记录操作顺序吧，经过一番思索后虽然理清了解题思路，但是在“如何用代码来实现”的问题上卡了老半天，想不通要怎么来保存路线，后来看到一种方法是 直接把每种可能的状态存储在队列中，只入队不出队，通过定义一个头指针和尾指针，指向接下来要判断的状态和要存入的状态的位置。然后我就想到可以直接把这些可能的状态按顺序存入结构体数组中，并在结构体中分别定义三个变量用来记录当前状态在数组中的位置、由前一种状态到当前状态所执行的操作、前一种状态的位置，这样一来很容易就能回溯得到完整的操作步骤。不过，无论是哪种方法，其实都有用到链表的思想吧。
自己初步的未能用代码实现的思路 + 别人已经用代码实现的思路 = 自己最后能用代码实现的思路。
要多看别人的代码，学习不同的解题方法，拓展自己的思维方式。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define INF 0x3f3f3f
#define zero 1e-7
typedef long long ll;
const int N=300;
int vis[N][N], cnt=0;
char step[7][15]={"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
struct node {
int now, v1, v2, ops, last;//当前状态所在位置，杯a、b的水量，由什么操作得到，进行该操作前的状态
}mp[N]={{0,0,0,0,0}};
queue<node> q;
int bfs(int a, int b, int c) {
// mp[0].now=0;//如果要统一初始化的话，只能是在定义的时候，否则只能逐个赋值
// mp[0].v1=0;
// mp[0].v2=0;
// mp[0].ops=0;
// mp[0].last=0;
q.push(mp[cnt++]);
while(!q.empty()) {
node temp=q.front();
q.pop();
if(temp.v1==c || temp.v2==c) {
printf("%d\n", vis[temp.v1][temp.v2]);
return temp.now;
}
for(int i=1; i<=6; i++) {
int x, y;
switch(i) {
case 1://把v1装满
x=a; y=temp.v2;
break;
case 2://把v2装满
x=temp.v1; y=b;
break;
case 3://把v1倒空
x=0; y=temp.v2;
break;
case 4://把v2倒空
x=temp.v1; y=0;
break;
case 5://把v1倒给v2
if(temp.v1+temp.v2<=b) {
x=0;
y=temp.v1+temp.v2;
}else {
x=temp.v1+temp.v2-b;
y=b;
}
break;
case 6://把v2倒给v1
if(temp.v1+temp.v2<=a) {
x=temp.v1+temp.v2;
y=0;
}else {
x=a;
y=temp.v1+temp.v2-a;
}
break;
}
if(!vis[x][y] && (x || y)) {
vis[x][y]=vis[temp.v1][temp.v2]+1;
mp[cnt].now=cnt;
mp[cnt].v1=x;
mp[cnt].v2=y;
mp[cnt].ops=i;
mp[cnt].last=temp.now;
q.push(mp[cnt++]);
//printf("x=%d, y=%d, cnt=%d, last=%d %s\n", x, y, cnt-1, mp[cnt-1].last, step[mp[cnt-1].ops]);
}
}
}
return -1;
}
int main() {
int a, b, c, st[N];//st数组记录操作顺序和步骤
memset(vis, 0, sizeof(vis));
scanf("%d %d %d", &a, &b, &c);
int z=bfs(a, b, c);
if(z==-1)
printf("impossible\n");
else {
int num=0;
while(mp[z].last!=z) {
st[num++]=mp[z].ops;
z=mp[z].last;
}
while(num--) {
printf("%s\n", step[st[num]]);
}
}
return 0;
}