第一次做的时候，我定义了一个结构体，用来表示一个壶，后来搜索的时候发现无法从壶之前的状态转移到现在的状态，这就尴尬了。然后去看了一下别人的题解，就ac了。 思路：一共有三种操作，两个壶，共六种操作，直接对这六种操作bfs，这个很好想。主要是我看的别人题解是把两个壶的状态保存在同一个结构体里。
最后搜索完做好标记递归输出就好
#include <iostream> #include <cstring> #include <string> using namespace std; int a,b,c; int book[101][101]; struct Pot { int a,b,step,par; string op; }; Pot que[5000]; int index; void calc(Pot& p,Pot& cur,int& tail, int head) { if(book[cur.a][cur.b] == 0) { cur.step = p.step + 1; cur.par = head; que[tail++] = cur; book[cur.a][cur.b] = 1; } } bool BFS() { int head = 0; int tail = 0; que[tail].a = que[tail].b = que[tail].step = 0; que[tail].par = -1; ++tail; book[0][0] = 1; while(head < tail) { Pot p = que[head++]; if(p.a == c || p.b == c) { cout << p.step << endl; index = head - 1; return true; } Pot cur; cur.a = a; cur.b = p.b; cur.op = "FILL(1)"; calc(p,cur,tail,head-1); cur.a = p.a; cur.b = b; cur.op = "FILL(2)"; calc(p,cur,tail,head-1); cur.a = 0; cur.b = p.b; cur.op = "DROP(1)"; calc(p,cur,tail,head-1); cur.a = p.a; cur.b = 0; cur.op = "DROP(2)"; calc(p,cur,tail,head-1); cur.b = p.b + p.a; cur.a = p.a - (b - p.b); cur.op = "POUR(1,2)"; if(cur.b > b) cur.b = b; if(cur.a < 0) cur.a = 0; calc(p,cur,tail,head-1); cur.a = p.a + p.b; cur.b = p.b - (a - p.a); cur.op = "POUR(2,1)"; if(cur.a > a) cur.a = a; if(cur.b < 0) cur.b = 0; calc(p,cur,tail,head-1); } cout << "impossible" <<endl; return false; } void Print(int index) { if(que[index].par == -1) return; Print(que[index].par); cout << que[index].op << endl; } int main() { while(cin >> a >> b >> c) { index = 0; memset(book,0,sizeof(book)); if(BFS()) Print(index); } return 0; }