Untitled
unknown
plain_text
18 days ago
3.7 kB
2
Indexable
Never
package Lesson_15; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Hugo_Di_Tau { static int T, N, C; static int spots[]; // Trang thai ghe ngoi tren tau static boolean visited[]; // Status Gate đã đc duyệt hay chưa static int gates[][]; // So luong nguoi dang wait at Gate static int answer; //Ham kiem tra xem cong do da mo de nguoi vao het chua // True: Open - False: Close public static boolean isOpened(){ for(int i = 0; i < 3; i++){ if(!visited[i]) return false; } return true; } // Khoang cach tu cong do den vi tri ben phai gan nhat // Neu khong con cho ngoi ben phai thi tra ve gia tri rat lon public static int distanceToRightSpot(int start){ for(int i = start; i <= N; i++){ if(spots[i] == -1 ) return i - start; } return 1000000; } // Khoang cach tu cong do den vi tri ben trai gan nhat public static int distanceToLeftSpot(int start){ for(int i = start; 1 <= i; i--){ if(spots[i] == -1 ) return start - i; } return 1000000; } public static void backTrack(int sum){ // Kiem tra cong da mo het chua ,neu da mo het tra ve gia tri if(isOpened()){ if(answer > sum) answer = sum; return; } for(int i = 0; i < 3; i++){ // Cong da dc mo thi bo qua if(visited[i]) continue; // Cong chua mo thi tham cong do va danh dau da tham visited[i] = true; int add = gates[i][1]; // Xep het nguoi tai cong do vao vi tri. De lai 1 nguoi cuoi cung de check for(int j = 0; j < gates[i][1] - 1; j++){ int left = distanceToLeftSpot(gates[i][0]); // Kc cong do den trai int right = distanceToRightSpot(gates[i][0]); // Kiem tra khoang cach khi them vao trai/ phai. Ben nao nho hon thi lay if(left < right) { spots[gates[i][0] - left] = i; add += left; } else { spots[gates[i][0] + right] = i; add += right; } } // Tra ve khoang cach nguoi cuoi cung cua cong do so voi ben trai/ phai int left = distanceToLeftSpot(gates[i][0]); int right = distanceToRightSpot(gates[i][0]); // Neu khoang cach do khac nhau thi check xem ben trai hay phai nho hon de ta xep if(left != right) { if(left < right) { spots[gates[i][0] - left] = i; add += left; } else { spots[gates[i][0] + right] = i; add += right; } backTrack(sum + add); } // Neu khoang cach bang nhau thi can dat thu vao ca 2 ben trai va phai else { add += left; spots[gates[i][0] + right] = i; backTrack(sum + add); spots[gates[i][0] + right] = -1; spots[gates[i][0] - left] = i; backTrack(sum + add); spots[gates[i][0] -left] = -1; } // Tra lai cong chua tham de backTrack lai visited[i] = false; // Tra lai vi tri cong do da ngoi for(int j = 1; j <= N; j++){ if(spots[j] == i) spots[j] = -1; } } } public static void main(String[] args) throws FileNotFoundException{ System.setIn(new FileInputStream("Hugo_Di_Tau")); Scanner scanner = new Scanner(System.in); T = scanner.nextInt(); for(int tc = 1; tc <= T; tc++){ N = scanner.nextInt(); gates = new int[3][2]; for(int i = 0; i < 3; i++){ gates[i][0] = scanner.nextInt(); // Vi tri cong gates[i][1] = scanner.nextInt(); // So luong nguoi trc cong } spots = new int[N+1]; visited = new boolean[N+1]; for(int i = 1; i <= N; i++){ spots[i] = -1; } answer = 10000; backTrack(0); System.out.println("Case #"+ tc ); System.out.println(answer); } } }
Leave a Comment