UVa 571 Jugs

想法：
　　題目沒說要最少步數(先輸出10次fill A empty A也可)，所以直接用DFS求解即可。

	#include <cstdio>
	#include <vector>
	#include <string>
	using namespace std;
	int A, B, N;
	vector<string> process;
	int visit[1005][1005];
	bool DFS(int a, int b)
	{
	visit[a][b] = 1;
	if (b == N) return 1;
	if (visit[A][b] == 0) {process.push_back("fill A"); if (DFS(A,b)) return 1; process.pop_back();}
	if (visit[a][B] == 0) {process.push_back("fill B"); if (DFS(a,B)) return 1; process.pop_back();}
	if (visit[0][b] == 0) {process.push_back("empty A"); if (DFS(0,b)) return 1; process.pop_back();}
	if (visit[a][0] == 0) {process.push_back("empty B"); if (DFS(a,0)) return 1; process.pop_back();}
	int pour_A, pour_B;
	if (b > (A-a)) {pour_A = A; pour_B = B - (A-a);}
	else {pour_A = a + b; pour_B = 0;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour B A");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}
	if (a > (B-b)) {pour_A = A - (B-b); pour_B = B;}
	else {pour_A = 0; pour_B = b + a;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour A B");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}
	return 0;
	}
	int main()
	{
	while (scanf("%d%d%d", &A, &B, &N) != EOF) {
	process.clear();
	for (int i = 0; i<1005; ++i)
	for (int j = 0; j<1005; ++j)
	visit[i][j] = 0;
	DFS(0,0);
	for (string &a : process)
	printf("%s\n", a.c_str());
	printf("success\n");
	}
	return 0;
	}

view raw [UVa] 571 Jugs.cpp hosted with ❤ by GitHub