Pots 廣搜 + 路徑回溯 POJ - 3414

題目來源：POJ - 3414

同類題目:POJ 3984 --迷宮問題

POJ 3984–迷宮問題題解連結,點選檢視

題意簡述：

給你A、B兩個瓶子，一個容量C，問如何才能用最少的操作倒出其中一個瓶子裝有C升的液體,輸出操作次數和操作序列。

你可以進行的操作有：

1、FILL：裝滿A或B

2、DROP：倒光A或者B

3、POUR：将A倒到B中，或者将B倒入A中

思路：

由于本題是需要最少的操作次數，，每個操作可能有6種情況，并且需要的是一個操作序列，是以考慮使用BFS枚舉六種情況+路徑回溯找出操作序列。

AC代碼：

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 2005;
int a, b, c;
int ans, len = 0, flag;
int vis[maxn][maxn];
string ops[6] = { "FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)" };
struct node {
	int x, y;  //目前a和b的狀态
	int pre;  //前一個操作
	int now; //目前操作順序 
	int op;	//目前操作的指令
	int step;
	node() {}
	node(int a, int b, int pr, int i, int oder, int s) {    //有參構造 
		x = a;
		y = b;
		pre = pr;
		now = i;
		op = oder;
		step = s;
	}
};
node road[maxn];
void ways(int now)
{
	stack<int> stk;
	int index = now;
	while (index != 0) {
		stk.push(road[index].op);
		index = road[index].pre;
	}
	while (!stk.empty()) {
		int t = stk.top();
		cout << ops[t] << endl;
		stk.pop();
	}
}
void bfs()
{
	flag = -1;
	int cnt = 0;
	queue<node> q;
	q.push(node(0, 0, -1, 0, 0, 0));
	vis[0][0] = 1;
	node p = q.front();
	road[len++] = p;
	while (!q.empty()) {
		node temp = q.front();
		q.pop();
		if (temp.x == c || temp.y == c) {   //找到一種情況 
			cout << temp.step << endl;
			ways(temp.now);
			return;
		}
		for (int i = 0; i < 6; i++) {
			if (i == 0) {  //fill a 形成狀态 temp.x a
				if (temp.x < a && vis[a][temp.y] == 0) { //水杯沒滿 并且目前這個狀态沒有出現過 
					vis[a][temp.y] = 1;
					node n(a, temp.y, temp.now, len, i, temp.step + 1);
					q.push(n);
					road[len++] = n;
				}
			}
			else if (i == 1) { // fill b  形成狀态 temp.x b 
				if (b > temp.y && vis[temp.x][b] == 0) {
					vis[temp.x][b] = 1;
					node n(temp.x, b, temp.now, len, i, temp.step + 1);
					q.push(n);
					road[len++] = n;
				}

			}
			else if (i == 2) {   // drop a   形成狀态0 temp.y 
				if (temp.x > 0 && vis[0][temp.y] == 0) {
					vis[0][temp.y] = 1;
					node n(0, temp.y, temp.now, len, i, temp.step + 1);
					q.push(n);
					road[len++] = n;
				}

			}
			else if (i == 3) {  //drop b 形成狀态 temp.x 0 
				if (temp.y > 0 && vis[temp.x][0] == 0) {
					node n(temp.x, 0, temp.now, len, i, temp.step + 1);
					q.push(n);
					road[len++] = n;
				}
			}
			// 目前的水沒滿 但是要将它裝滿 需要再裝a-x  如果可以倒過去的水大于a-x 則隻倒a-x  如果能倒過去的水小于a-x 則全部倒過去 
			else if (i == 4) {   //a->b倒水 則temp.x -= pour  temp.y += pour
				if (temp.x > 0 && temp.y < b) {
					int pour = min(temp.x, b - temp.y);
					if (vis[temp.x - pour][temp.y + pour] == 0) {
						vis[temp.x - pour][temp.y + pour] = 1;
						node n(temp.x - pour, temp.y + pour, temp.now, len, i, temp.step + 1);
						q.push(n);
						road[len++] = n;
					}

				}
			}
			else {   //b->a倒水 則temp.x += pour  temp.y -= pour
				if (temp.y > 0 && temp.x < a) {
					int pour = min(temp.y, a - temp.x);
					if (vis[temp.x + pour][temp.y - pour] == 0) {
						vis[temp.x + pour][temp.y - pour] = 1;
						node n(temp.x + pour, temp.y - pour, temp.now, len, i, temp.step + 1);
						q.push(n);
						road[len++] = n;
					}
				}
			}
		}
	}
	cout << "impossible" << endl;
}
int main()
{
	cin >> a >> b >> c;
	memset(vis, 0, sizeof(vis));
	bfs();
	return 0;
}
/*
3 5 4
FILL(2)    0 5
POUR(2,1)  3 2
DROP(1)    0 2
POUR(2,1)  2 0
FILL(2)    2 5
POUR(2,1)  3 4
*/