Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
7
Indexable
#include<iostream>

using namespace std;

int t,n,dem,s,cnt,longmax,rc,cc,rh,ch,ans;
int check[12];
int mangr[12];
int mangc[12];
int map[12][12];


int ttd(int a , int b){
	return (a>=b)? (a-b) : (b-a);
}

int dis(int a, int b){
	return (ttd(mangr[a],mangr[b]) + ttd(mangc[a], mangc[b]));
}

void bt(int current_position, int current_long){
	if(cnt==n) {
		current_long+= map[n+1][current_position];
		if(current_long<longmax) longmax=current_long;
	}
	else{
		for(int i=1;i<=n;i++){
			if(check[i]==0 && (current_long+map[i][current_position]<longmax)){
				check[i]=1;
				cnt++;
				current_long+=map[i][current_position];
				bt(i,current_long);
				check[i]=0;
				cnt--;
				current_long-=map[i][current_position];
			}
		}
	}

}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> rc >> cc >> rh >> ch;
		cin >> n;
		for(int i=1;i<=n;i++){
			cin >> mangr[i] >> mangc[i];
		}
		mangr[0]=rc; mangc[0]=cc;
		mangr[n+1]=rh; mangc[n+1]=ch;
		ans=0;
		for(int i=0;i<=n+1;i++){
			for(int j=0;j<=n+1;j++) map[i][j]=dis(i,j);
		}
		longmax=2000000000;

		cnt=0;
		bt(0,map[0][0]);
		cout << "Case #" << tc << " " << longmax << endl;
	}

	return 0;
}
Editor is loading...
Leave a Comment