Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include<iostream>

using namespace std;

int N;
int Sx, Sy, Hx, Hy;

int mapX[15];
int mapY[15];
int visited[15];
int minDistance;

int d2p(int x1, int y1, int x2, int y2) // distance 2 point
{
	int abs1 = x1 - x2;
	int abs2 = y1 - y2;
	if(abs1 < 0)	abs1 *= -1;
	if(abs2 < 0)	abs2 *= -1;
	return abs1 + abs2;
}

void backTrack(int k, int x, int y, int sumDistance)
{
	if(k == N)
	{
		int dToHome =  d2p(x, y,Hx,Hy);
		sumDistance += dToHome;
		if(sumDistance < minDistance)	minDistance = sumDistance;
		return;
	}	

	if(sumDistance > minDistance)	return;

	for (int i = 0; i < N; i++)
	{
		if(visited[i] == 0)
		{
			visited[i] = 1;
			backTrack(k +1, mapX[i], mapY[i], sumDistance + d2p(mapX[i],mapY[i], x,y));
			visited[i] = 0;
		}
	}
}

void reset()
{
	for(int i = 0; i < 15; i++)
	{
		visited[i] = 0;
	}
}

void input()
{
	cin>>Sx>>Sy>>Hx>>Hy;
	cin>>N;
	for(int i =0; i < N; i++)
	{
		cin>>mapX[i]>>mapY[i];
	}
}

int main()
{
	freopen("Text.txt", "r", stdin);
	int T;
	cin>>T;

	for(int tc =1; tc <= T; tc++)
	{
		input(); // nhap Sx,Sy,Hx,Hx, N va N cap toa do piza
		minDistance = 999999999;

		backTrack(0,Sx,Sy,0);
		
		cout<<"Case #"<<tc<<" "<<minDistance<<endl;
	}
	return 0;
}