题目链接：点击打开链接
题意：
有两个壶，分别有A, B升水，问通过三个操作FILL, DROP, POUR，是否能使得这两个壶中有一个壶刚好有C升水。输出最少的操作步数，以及每一步具体的操作。
思路：
bfs，得到最少步数。因为要输出具体步骤，在bfs过程中要记录之前的操作，设置pre指针，指向之前的节点，路径的记录直接用了STL的stack...
在bfs中，我把每一步操作细分，然后用了函数指针数组，方便bfs。
然后dfs，输出路径。
wa了两发，发现忘记输出impossible了。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> using namespace std; int a, b, c; const char str[6][10] = { "FILL(1)", "FILL(2)", "POUR(1,2)", "POUR(2,1)", "DROP(1)", "DROP(2)" }; struct Node { int a, b; int order, cnt; Node *pre; Node(int a, int b, int order, int cnt, Node*pre){ this->a = a; this->b = b; this->order = order; this->cnt = cnt; this->pre = pre; } }; void fill1(Node &tmp){ tmp.a = a; } void fill2(Node &tmp){ tmp.b = b; } void pour1to2(Node &tmp){ int cha = b - tmp.b; if(cha < tmp.a){ tmp.b = b; tmp.a -= cha; } else{ tmp.b += tmp.a; tmp.a = 0; } } void pour2to1(Node &tmp){ int cha = a - tmp.a; if(cha < tmp.b){ tmp.a = a; tmp.b -= cha; } else{ tmp.a += tmp.b; tmp.b = 0; } } void drop1(Node &tmp){ tmp.a = 0; } void drop2(Node &tmp){ tmp.b = 0; } void (*menu[])(Node &tmp) = {fill1, fill2, pour1to2, pour2to1, drop1, drop2}; const int MAXN = 100 + 10; bool vis[MAXN][MAXN]; void dfs(Node* temp){ if(temp->order==-1 || temp->pre==NULL) return; dfs(temp->pre); printf("%s\n", str[temp->order]); } void bfs(){ queue<Node> q; stack<Node> ans; q.push(Node(0, 0, -1, 0, NULL)); //a, b, order, cnt, pre; memset(vis, 0, sizeof(vis)); while(!q.empty()){ ans.push(q.front()); q.pop(); Node temp = ans.top(); if(temp.a==c || temp.b==c){ printf("%d\n", temp.cnt); dfs(&temp); return; } for(int i=0; i<6; ++i){ Node another = temp; menu[i](another); if(vis[another.a][another.b]) continue; another.pre = &ans.top(); another.order = i; ++another.cnt; q.push(another); vis[another.a][another.b] = true; } } printf("impossible\n"); } int main(){ scanf("%d%d%d", &a, &b, &c); bfs(); return 0; }