huguquanlytautu

 avatar
quoc14
c_cpp
a month ago
2.6 kB
3
Indexable
Never
caidat
#include <iostream>

using namespace std;

int n;
int minans;

struct Door{
	int posDoor;
	int cCus;
};

int kt[3];

Door doors[4];
int isset[10002];
int tt[4];



void backtrack(int index, int sumd)
{
	if (index == 4)
	{
		if (minans > sumd) minans = sumd;
	/*	for (int i = 0; i <= n+1; i++)
			cout << isset[i] <<" ";
		cout << sumd << endl;*/
		return;
	}
	int iddoor = tt[index];
	Door curent =  doors[iddoor];

	int left = curent.posDoor;
	int right = curent.posDoor;
	for (int i = 1; i < curent.cCus; i++)
	{
		while (isset[left] != 0 && left>0) left--;
		while (isset[right] != 0 && right <= n) right++;
		if (left == 0)
			{
				isset[right++] = iddoor;
				sumd +=  right -  curent.posDoor;
			}
		else if (right == n+1) 
			{
				isset[left--] = iddoor;
				sumd += curent.posDoor - left;
			}
		else
		{
			if (curent.posDoor - left < right - curent.posDoor)
			{
				isset[left--] = iddoor;
				sumd += curent.posDoor - left;
			}
			else
			{
				isset[right++] = iddoor;
				sumd +=  right -  curent.posDoor;
			}
		}
	}

	while (isset[left] != 0 && left>0) left--;
	while (isset[right] != 0 && right <= n) right++;

	if (left == 0) 
	{
			isset[right++] = iddoor;
			sumd +=  right -  curent.posDoor;
			backtrack(index+1,sumd);
	}
	else if (right == n+1) 
		{
			isset[left--] = iddoor;
			sumd += curent.posDoor - left;
			backtrack(index+1, sumd);
		}
		else
		{
			if (curent.posDoor - left == right - curent.posDoor)
			{
				sumd += curent.posDoor - left + 1;
				isset[left] = iddoor;
				backtrack(index+1, sumd);
				isset[left] = 0;
				isset[right] = iddoor;
				backtrack(index+1, sumd);
			} else
			{
				if (curent.posDoor - left < right - curent.posDoor)
				{
					isset[left--] = iddoor;
					sumd += curent.posDoor - left;
				}
				else
				{
					isset[right++] = iddoor;
					sumd +=  right -  curent.posDoor;
				}
				backtrack(index+1, sumd);
			}
		}

	for (int i = 1; i <= n; i++)
	if (isset[i] == iddoor)
	{
		isset[i] = 0;
	}
}

void back(int index)
{
	if (index == 4)
	{
		backtrack(1, 0);
		return;
	}
	for (int i = 1; i<=3; i++)
	if (kt[i] == 0)
	{
		kt[i] = 1;
		tt[index] = i;
		back(index + 1);
		kt[i] = 0;
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> n;
		for (int i = 1; i <= 3; i++)
			cin >> doors[i].posDoor >> doors[i].cCus;
		minans = 9999999;
		back(1);
		cout << "Case #"<<tc << endl << minans << endl;
	}
	
	//back(1);
	

	return 0;
}
Leave a Comment