SPOJ.COM - Thuật toán bài CTAIN - Containers

#include<iostream>
using namespace std;

const int MAX = 5;
const int MAX_QUEUE = 1000000;
const int MAX_INT = 1 << 30;
const int MAX_STATE = 50;

int  N;				//số lượng thùng
int Capacity[MAX];	//dung lượng mối thùng
int Water[MAX];		//lượng nước hiện tại mỗi thùng
int Need[MAX]; 		//lượng nước cần
int Answer;			//kết quả
bool Flag, Finish;

// Đánh dấu trạng thái
int  State[MAX_STATE][MAX_STATE][MAX_STATE][MAX_STATE];

typedef struct Point
{
	int *water;
	int step;
	Point():step(0),water(0){}
	Point(int st, int *wa):step(st),water(wa){}
}Point;

Point queue[MAX_QUEUE];
int fr, re, leng;

/**
* copy mảng: từ mảng src sang mảng dst*/
void CpyArray(int *dst, int *src)
{
	for(int i = 0; i < N; i++)
		dst[i] = src[i];
}

// implement hàng đợi vòng
void Enqueue(Point p)
{
	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr = (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

/**
* Lấy giá trị của mảng 4 chiều tại một trạng thái
*/
int GetValueState(int *tmp)
{
	int a,b,c,d;
	a = b = c = d = 0;

	if(N == 1) a = tmp[0];
	else if(N == 2) {a = tmp[0]; b = tmp[1];}
	else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];}
	else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];}

	return State[a][b][c][d];
}

/**
* Xét giá trị value cho mảng 4 chiều tại trạng thái cho trước
*/
void SetValueState(int *tmp, int value)
{
	int a,b,c,d;
	a = b = c = d = 0;

	if(N == 1) a = tmp[0];
	else if(N == 2) {a = tmp[0]; b = tmp[1];}
	else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];}
	else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];}

	State[a][b][c][d] = value;
}

// Implement BFS
void BFS(Point st)
{
	fr = re = leng = 0;
	SetValueState(st.water,0);
	Enqueue(st);

	while(leng > 0)
	{
		Point p = Dequeue();

		// Duyệt các thùng và thực hiện 3 hành động
		for(int i = 0; i < N; i++)
		{
			// Hành động 1: đổ hết nước đi
			int old_water = p.water[i];
			p.water[i] = 0;

			int *tmp1 = new int[N];
			CpyArray(tmp1, p.water);

			// Kiểm tra xem trạng thái này đã có chưa
			// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
			if(GetValueState(tmp1) == MAX_INT)
			{
				SetValueState(tmp1, p.step + 1);
				Enqueue(Point(p.step + 1, tmp1));
			}
			p.water[i] = old_water;

			// Hành động 2: Đổ đầy bằng 1 thùng khác
			// Hành động này chỉ thực hiện khi thùng chưa đầy
			if(p.water[i] < Capacity[i])
			{
				// thử đổ đầy bằng các thùng còn lại
				for(int j = 0; j < N; j++)
				{
					if(j == i) continue;
					if(Capacity[i] - p.water[i] <= p.water[j])
					{
						int old_water1 = p.water[i], old_water2 = p.water[j];
						p.water[j] = p.water[j] - (Capacity[i] - p.water[i]);
						p.water[i] = Capacity[i];

						int *tmp2 = new int[N];
						CpyArray(tmp2,p.water);

						// Kiểm tra xem trạng thái này đã có chưa
						// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
						if(GetValueState(tmp2) == MAX_INT)
						{
							SetValueState(tmp2,p.step+1);
							Enqueue(Point(p.step+1,tmp2));
						}
						p.water[i] = old_water1;
						p.water[j] = old_water2;
					}
				}
			}

			//Hành động 3: Đổ hết nước sang thùng khác nếu đủ chỗ
			//Xét thử các thùng
			for(int j = 0; j < N; j++)
			{
				if(j == i) continue;
				if(Capacity[j] - p.water[j] >= p.water[i])
				{
					int old_water1 = p.water[i], old_water2 = p.water[j];
					p.water[j] = p.water[j] + p.water[i];
					p.water[i] = 0;

					int *tmp3 = new int[N];
					CpyArray(tmp3,p.water);

					// Kiểm tra xem trạng thái này đã có chưa
					// nếu giá trị tại đó là MAX_INT nghĩa là chưa có
					if(GetValueState(tmp3) == MAX_INT)
					{
						SetValueState(tmp3,p.step+1);
						Enqueue(Point(p.step+1,tmp3));
					}
					p.water[i] = old_water1;
					p.water[j] = old_water2;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		cin >> N;
		for(int i = 0; i < N; i++)
		{
			cin >> Capacity[i];
			Water[i] = Capacity[i];
		}

		for(int i = 0; i < N; i++)
			cin >> Need[i];

		Answer = MAX_INT;
		for(int i = 0; i < MAX_STATE; i++)
			for(int j = 0; j < MAX_STATE; j++)
				for(int k = 0; k < MAX_STATE; k++)
					for(int m = 0; m < MAX_STATE; m++)
						State[i][j][k][m] = MAX_INT;

		BFS(Point(0, Water));

		Answer = GetValueState(Need);

		if(Answer == MAX_INT) cout << "NO" << endl;
		else cout << Answer << endl;
	}
	return 0;
}