Untitled
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