Untitled

mail@pastecode.io avatar
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