POJ3414Pots(倒水问题BFS+打印路径）

就是给你A&＃xff0c; B两个杯子&＃xff0c;及他们的最大容量&＃xff0c;三种操作方法&＃xff0c;让你判断最少用多少此方法可以让任意一个被子里装有 C 升水。并打印路径。

分析

这里很容易想到广搜&＃xff0c;设初始状态为&＃xff08;i&＃xff0c;j&＃xff09;&＃xff0c;一共就只有六种变化
A杯倒满&＃xff0c;B杯倒满&＃xff0c;A杯倒出完&＃xff0c;B杯倒出完&＃xff0c;A到给B&＃xff0c;B到给A。
任意一种状态i 或者 j达到 C 就停止&＃xff0c;注意要打印路径&＃xff0c;我这里用一个string存的操作顺序。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#pragma comment (linker, "/STACK:256000000")
using namespace std;
#define db(x) cout<typedef long long ll;
const int N &＃61; 100 &＃43; 10;
const int INF &＃61; 0x3f3f3f;int flag &＃61; 0;
int a, b, c; //A, B, c, 盒子容量
int vis[N][N]; //保存容量状态
string str[10] &＃61; {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};struct node
{int x, y; //A, B盒子容量int step; //操作数string s; //操作路径node(int x, int y, int step, string s):x(x),y(y),step(step),s(s){}
};void bfs()
{queue<node> q;vis[0][0] &＃61; 1;q.push(node(0, 0, 0, "0"));while(!q.empty()){node temp &＃61; q.front();q.pop();if(temp.x &＃61;&＃61; c || temp.y &＃61;&＃61; c){flag &＃61; 1;cout << temp.step << endl;for (int i &＃61; 1; i < temp.s.length(); i&＃43;&＃43;){cout << str[temp.s[i] - &＃39;0&＃39;] << endl;}return;}if(temp.x < a){ //将第一个瓶子装满if(!vis[a][temp.y]){vis[a][temp.y] &＃61; 1;q.push(node(a, temp.y, temp.step &＃43; 1, temp.s &＃43; "1"));}}if(temp.y < b){ //将第二个瓶子装满if(!vis[temp.x][b]){vis[temp.x][b] &＃61; 1;q.push(node(temp.x, b, temp.step &＃43; 1, temp.s &＃43; "2"));}}if(temp.x !&＃61; 0){ //将第一个瓶子倒完if(!vis[0][temp.y]){vis[0][temp.y] &＃61; 1;q.push(node(0, temp.y, temp.step &＃43; 1, temp.s &＃43; "3"));}}if(temp.y !&＃61; 0){ //将第二个瓶子装满if(!vis[temp.x][0]){vis[temp.x][0] &＃61; 1;q.push(node(temp.x, 0, temp.step &＃43; 1, temp.s &＃43; "4"));}}if(temp.x !&＃61; 0 && temp.y < b){ //将第一个瓶子倒进第二个瓶子int xx, yy;if(temp.x <&＃61; b - temp.y){xx &＃61; 0;yy &＃61; temp.y &＃43; temp.x;}else{yy &＃61; b;xx &＃61; temp.x - b &＃43; temp.y;}if(!vis[xx][yy]){vis[xx][yy] &＃61; 1;q.push(node(xx, yy, temp.step &＃43; 1, temp.s &＃43; "5"));}}if(temp.y !&＃61; 0 && temp.x < a){ //将第二个瓶子倒进第一个瓶子int xx, yy;if(temp.y <&＃61; a - temp.x){yy &＃61; 0;xx &＃61; temp.x &＃43; temp.y;}else{xx &＃61; a;yy &＃61; temp.y - a &＃43; temp.x;}if(!vis[xx][yy]){vis[xx][yy] &＃61; 1;q.push(node(xx, yy, temp.step &＃43; 1, temp.s &＃43; "6"));}}}
}int main()
{cin >> a >> b >> c;bfs();if(!flag)cout << "impossible" << endl;return 0;
}