Untitled
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