Untitled

 avatar
unknown
plain_text
a year ago
2.8 kB
5
Indexable
import java.util.Scanner;





public class Solution {
	static int N, people[], door[], kc[][], check[], bit[], visit[];
	static int Max;

	static void print(int[] kc) {
		for (int i = 1; i < N + 1; i++) {

			System.out.print(kc[i] + " ");

		}
		System.out.println();
	}


	static void backtrack(int indext,int sum) {
		if (indext == 4) {
			Max = Math.min(Max, sum);
			//visit = new int[N+1];
			return;

		}
		for(int s = 1; s<= 3; s++){
			if(check[s] == 0){
				
				for (int k = 0; k < 2; k++) {
					int dor = door[s];// cua mo
					int guse = people[dor];
					int cout = 0;
					int value = 0;
					if (k == 0) {
						check[s] = 1;
						//.................
						while (guse > 0) {
							// xet ben trai
							int l = dor - cout;
							int r = dor + cout;
							// xet phai
						
							if (l >= 1 && visit[l] == 0) {
								visit[l] = dor;
								value= value + cout +1;
								guse--;
							}
							// xet trai
							else if (r <= N && visit[r] == 0 ) {
								visit[r] = dor;
								value= value + cout +1;
								guse--;

							} else if ( (r <= N && visit[r] != 0)|| (l>= 1 && visit[l] != 0)) {
								cout++;
							}

						}
						backtrack(indext + 1,sum +value);
						check[s] =0;
						for (int i = 1; i <= N; i++) {
							if (visit[i] == dor)
								visit[i] = 0;

						}

					} else {
						//.................................
						check[s] = 1;
						while (guse > 0) {
							// xet ben trai
							int l = dor - cout;
							int r = dor + cout;
							// xet phai
							if (r <= N && visit[r] == 0) {
								visit[r] = dor;
								value= value + cout +1;
								guse--;
								// xet trai
							} else if (l >= 1 && visit[l] == 0) {
								visit[l] = dor;
								value= value + cout +1;
								guse--;
							} else  {
								cout++;
							}

						}
						backtrack(indext + 1, sum +value);
						check[s] = 0;
						for (int i = 1; i <= N; i++) {
							if (visit[i] == dor)
								visit[i] = 0;

						}
					}
				}
				
			}
			
		}
		

	}

	public static void main(String[] args)  {
		
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int t = 1; t <= T; t++) {
			N = scanner.nextInt();
			door = new int[4];
			people = new int[N + 1];
			kc = new int[4][N + 1];
			for (int i = 1; i <= 3; i++) {
				int x = scanner.nextInt();
				door[i] = x;
				people[x] = scanner.nextInt();
			}
			for (int i = 1; i <= 3; i++) {
				int k = door[i];
				for (int j = 1; j <= N; j++) {
					kc[i][j] = Math.abs(k - j) + 1;

				}
			}
			bit = new int[4];
			check = new int[5];
			visit = new int[N +1];
			Max = 10000;
			backtrack(1,0);
			System.out.println("Case #" + t );
			System.out.println(Max);

		}

	}

}
Editor is loading...
Leave a Comment