Untitled
unknown
plain_text
a year ago
3.0 kB
2
Indexable
Never
#include <iostream> #define MIN 999999999 using namespace std; int n, p, c; int visitedCua[5]; int arrCua[5]; int arrGhe[61]; int visitedGhe[61]; int Min; typedef struct Point{ int x, y; }; Point G[5]; int ttd(int num){ if(num<0) return 0-num; return num; } void BackTrackGhe(int c, int kc){ if(c == 4){ Min = min(Min, kc); } if(kc>=Min){ return; } for(int i=1; i<=3; i++){ if(G[i].y > 0){ int kc1 = 0; int L = G[i].x - 1; int R = G[i].x + 1; if(visitedGhe[G[i].x] == 0){ visitedGhe[G[i].x] = i; G[i].y--; kc1++; } while(G[i].y > 0 && (L >= 1 || R <= n)){ if(G[i].y == 1 && R <= n && L >= 1 && visitedGhe[R] == 0 && visitedGhe[L] == 0){ break; } else{ if(L>=1 && visitedGhe[L] == 0){ visitedGhe[L] = i; G[i].y--; kc1 += ttd(L-G[i].x) + 1; } if(R<=n && visitedGhe[R] == 0){ visitedGhe[R] = i; G[i].y--; kc1 += ttd(R-G[i].x) + 1; } L--; R++; } } if(G[i].y == 1){ visitedGhe[L] = i; G[i].y--; BackTrackGhe(c+1, kc1 + ttd(L-G[i].x) + 1 + kc); G[i].y++; visitedGhe[L] = 0; visitedGhe[R] = i; G[i].y--; BackTrackGhe(c+1, kc1 + ttd(R-G[i].x) + 1 + kc); G[i].y++; visitedGhe[R] = 0; } else{ BackTrackGhe(c+1, kc + kc1); } for(int j = L+1; j < R; j++){ if(visitedGhe[j] == i){ visitedGhe[j] = 0; G[i].y++; } } } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n; for(int i=1; i<=3; i++){ cin >> G[i].x >> G[i].y; } for(int i=1; i<=n; i++){ visitedGhe[i] = 0; } Min = MIN; BackTrackGhe(1, 0); cout << "Case #" << tc << endl; cout << Min << endl; } return 0; } 50 10 4 5 6 2 10 2 10 8 5 9 1 10 2 24 15 3 20 4 23 7 39 17 8 30 5 31 9 60 57 12 31 19 38 16 10 2 2 8 3 5 2 10 9 3 3 3 5 2 10 8 8 2 1 6 1 10 2 2 5 2 3 2 10 2 2 5 2 4 2 20 12 5 19 6 10 2 20 16 4 15 3 4 4 20 14 2 5 6 2 5 20 8 4 5 4 3 2 20 4 5 2 5 10 6 20 11 5 3 5 9 3 20 5 4 9 3 7 4 20 11 4 7 3 2 4 20 4 1 5 3 15 5 20 17 1 12 4 9 3 30 14 9 18 3 29 10 30 12 10 4 9 6 5 30 1 4 28 7 27 2 30 6 1 15 10 23 8 30 4 7 28 1 13 2 30 7 6 6 5 18 2 30 23 2 21 5 11 7 30 11 8 28 8 12 8 30 18 10 4 10 6 9 30 12 7 19 7 3 1 40 14 1 9 4 21 5 40 11 11 40 8 25 10 40 36 11 2 12 3 17 40 15 2 21 9 37 20 40 29 3 5 2 2 11 40 19 6 21 13 29 11 40 14 11 9 4 4 11 40 18 10 14 12 35 8 40 12 10 1 6 10 10 40 24 8 25 6 9 1 50 3 6 46 8 36 12 50 38 9 15 1 4 3 50 19 15 31 2 47 6 50 49 9 10 7 8 11 50 43 15 39 10 30 7 60 12 17 16 12 29 3 60 55 20 33 20 16 20 60 27 10 36 3 54 5 60 37 20 42 20 19 20 60 60 13 18 10 37 16