Untitled

 avatar
unknown
plain_text
a year ago
2.7 kB
3
Indexable
#include <iostream>
using namespace std;
struct vitri
{
	int row;
	int col;
};
int T;
int N;
vitri start;
vitri end1;
vitri A[10];
vitri B[10];
int KC[10];
int min_kc;
int visit_hole[10];
int visit_cong[10][2];
int th;
int abs(int n ){
	if(n < 0){
		return -n;
	}
	return n;
}

int khoang_cach(vitri x, vitri y){
	return abs(x.row - y.row) + abs(x.col - y.col);
}

int hoanvi[6];
int tophoanvi;

void BT(int index, int curx, int cury, int score){
	vitri st;
	st.row = curx;
	st.col = cury;
	int check = khoang_cach(st, end1);
	//dk dung
	if(score > min_kc){
		return;
	}
	if(index == N){
		
	/*cout<< endl;
		cout << "th "<< th<< endl;
		for (int i = 0; i < tophoanvi; i++) cout << hoanvi[i] << "-";
		cout <<endl;*/
		th++;
		if(score + check <= min_kc){
			min_kc = score + check;
			// << "min " << min_kc << endl;
		}
		return;
	}

	//trang thai
	for(int i = 0; i < N; i++){
			for(int k = 0; k < 2; k++){
				if(k == 0 ){ // chon cong A
					visit_cong[i][0] = 1;

					hoanvi[tophoanvi] = i + 1;
					tophoanvi++;

					int k_c = khoang_cach(st, A[i]);
					BT(index+1, B[i].row, B[i].col, score + KC[i] + k_c);
					visit_cong[i][0] = 0;

					tophoanvi--;
					hoanvi[tophoanvi] = 0;
				}
				else { // chon cong B
					visit_cong[i][1] = 1;

					hoanvi[tophoanvi] = i + 1;
					tophoanvi++;

					int k_c = khoang_cach(st, B[i]);
					BT(index+1, A[i].row, A[i].col, score + KC[i] + k_c);
					visit_cong[i][1] = 0;
					
					tophoanvi--;
					hoanvi[tophoanvi] = 0;
				}

			}
		BT(index + 1, curx, cury, score);
	}

}


int main(){
	int score[50];
	//open("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; t++){
		cin >> N;
		cin >> start.row >> start.col;
		cin >> end1.row >> end1.col;
		for(int i = 0; i < N; i++){
			cin >> A[i].row >> A[i].col;
			cin >> B[i].row >> B[i].col;
			cin >> KC[i];

			visit_cong[i][0] = 0;
			visit_cong[i][1] = 0;
			hoanvi[i] = 0;
		}
		tophoanvi = 0;
		th = 0;
		min_kc = khoang_cach(start, end1);
		BT(0, start.row, start.col, 0);
		cout << "#" << t << " " << min_kc << endl;
		score[t-1] = min_kc;
	}

	//open("output.txt", "r", stdin);

	int diem = 0;
	int result[51];

	int wrongcase[51] = {0};
	for (int i = 0; i < 50; i++) {
		cin >> result[i];
		if (result[i] == score[i]) diem++;
		else wrongcase[i] = i + 1;
	}

	cout << "Your score: " << diem << "/50" << endl;
	for (int i = 0; i < 50; i++) {
		if (wrongcase[i] != 0) {
			cout << "Testcase " << wrongcase[i] << ": ";
			cout << score[i] << "-" << result[i];
			cout << endl;
		}
	}

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