思路：这可真是我目前写过最长的题目了，虽然很多可以复制（学艺不精T-T）。。。
其实思路还是很简单的，就是6种情况，各种倒来倒去，然后记录下路径，我的方法是用一张图来表示，有没有走到过，然后图上每个位置都存着父节点的位置，以及父节点怎么达到，如果找到了逆序输出，如果没找到impossible，具体的看代码吧；
代码如下：
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <sstream>
#define esp 1e-4
using namespace std;
int A, B, C;
int ans;
struct node
{
int x, y;//代表现在1号杯子跟2号杯子的状态
int fx, fy;//代表上一个状态
string to;//代表从上一个状态怎么到当前的状态
int step;//到达的时间
};
node chart[110][110];
bool vis[110][110];
int judge(int x, int y)
{
if (x == C || y == C)
return 1;
else
return 0;
}
void solve(int x, int y, int step)
{
ans = step;
cout << step << endl;
string temp[10000];
int time = 0;
while (step--)
{
node kkk=chart[x][y];
temp[time] = kkk.to;
x = kkk.fx;
y = kkk.fy;
time++;
}
for (int i =ans - 1; i >= 0; i--)
{
cout << temp[i] << endl;
}
}
void bfs()
{
node temp;
queue<node> q;
temp.x = 0;
temp.y = 0;
temp.step = 0;
vis[0][0] = true;
q.push(temp);
while (!q.empty())
{
node then;
//倒空1号瓶
if (!vis[0][q.front().y])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.to = "DROP(1)";
then.x = 0;
then.y = q.front().y;
then.step = q.front().step + 1;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "DROP(1)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
//倒空2号瓶
if (!vis[q.front().x][0])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.to = "DROP(2)";
then.y = 0;
then.x = q.front().x;
then.step = q.front().step + 1;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "DROP(2)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
//倒满1号瓶
if (!vis[A][q.front().y])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.to = "FILL(1)";
then.x = A;
then.y = q.front().y;
then.step = q.front().step + 1;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "FILL(1)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
//倒满2号瓶
if (!vis[q.front().x][B])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.to = "FILL(2)";
then.x = q.front().x;
then.y = B;
then.step = q.front().step + 1;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "FILL(2)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
//把1号瓶倒入2号瓶
if (q.front().x + q.front().y <= B)//如果倒的下
{
if (!vis[0][q.front().x + q.front().y])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.step = q.front().step + 1;
then.to = "POUR(1,2)";
then.x = 0;
then.y = q.front().x + q.front().y;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "POUR(1,2)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
}
else//如果倒不下
{
if (!vis[q.front().x + q.front().y - B][B])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.step = q.front().step + 1;
then.to = "POUR(1,2)";
then.x = q.front().x + q.front().y - B;
then.y = B;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "POUR(1,2)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
}
//把2号瓶倒入1号瓶
if (q.front().x + q.front().y <= A)//到的下
{
if (!vis[q.front().x + q.front().y][0])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.step = q.front().step + 1;
then.to = "POUR(2,1)";
then.x = q.front().x + q.front().y;
then.y = 0;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "POUR(2,1)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
}
else
{
if (!vis[A][q.front().x + q.front().y - A])
{
then.fx = q.front().x;
then.fy = q.front().y;
then.step = q.front().step + 1;
then.to = "POUR(2,1)";
then.x = A;
then.y = q.front().x + q.front().y - A;
vis[then.x][then.y] = true;
chart[then.x][then.y].fx = q.front().x;
chart[then.x][then.y].fy = q.front().y;
chart[then.x][then.y].to = "POUR(2,1)";
if (judge(then.x, then.y))
{
solve(then.x, then.y, then.step);
break;
}
q.push(then);
}
}
//cout << q.front().fx << q.front().fy << q.front().step << q.front().to << q.front().x << q.front().y << endl;
q.pop();
}
}
int main()
{
while (cin >> A >> B >> C)
{
memset(vis, 0, sizeof(vis));
ans = -1;
bfs();
if (ans == -1)
{
cout << "impossible\n";
}
}
/*
3 5 4
*/
return 0;
}
版权声明：本文为qq_39562952原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。