Untitled
plain_text
a month ago
2.9 kB
2
Indexable
Never
package hugo_di_tau; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, res, sum; static int[] a; static int[][] hoanvi = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } }; static int[] door, pass; public static boolean checkOut(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) { return false; } return true; } public static void backTrack(int k, int stt, int hv, int d) {// k so khach// // stt mo,// // id 0-5 if (d >= res) { return; } if (k == sum) { res = Math.min(res, d); return; } int index = door[hoanvi[hv][stt]]; int tmp = k + 1; for (int i = stt - 1; i >= 0; i--) { tmp -= pass[hoanvi[hv][i]]; } int newstt = tmp == pass[hoanvi[hv][stt]] ? stt + 1 : stt; if (a[index] == 0) { a[index] = 1; backTrack(k + 1, newstt, hv, d + 1); a[index] = 0; } else { int l = index - 1, r = index + 1; while (l >= 0 && a[l] != 0) l--; while (r < n && a[r] != 0) r++; if (l >= 0 && r < n) { // khach le va 2 ben deu trong va chua toi vi tri cua ke tiep if (index - l == r - index && newstt == stt + 1) { a[l] = 1; a[l] = 1; backTrack(k + 1, newstt, hv, d + (index - l + 1)); a[l] = 0; a[r] = 1; backTrack(k + 1, newstt, hv, d + (r - index + 1)); a[r] = 0; } else {// khach chan uu tien ben gan int tmp_index = index - l > r - index ? r : l; int tmp_d = Math.abs(index - tmp_index) + 1; a[tmp_index] = 1; backTrack(k + 1, newstt, hv, d + tmp_d); a[tmp_index] = 0; } } else if (l >= 0) { a[l] = 1; backTrack(k + 1, newstt, hv, d + (index - l + 1)); a[l] = 0; } else if (r < n) { a[r] = 1; backTrack(k + 1, newstt, hv, d + (r - index + 1)); a[r] = 0; } } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); a = new int[n]; door = new int[3]; pass = new int[3]; sum = 0; for (int i = 0; i < 3; i++) { door[i] = scanner.nextInt() - 1; pass[i] = scanner.nextInt(); sum += pass[i]; } res = Integer.MAX_VALUE; for (int i = 0; i < 6; i++) { backTrack(0, 0, i, 0); } // backTrack(0, 0, 0, 0); // for (int i = 0; i < n; i++) { // System.out.print(a[i] + " "); // } // System.out.println(); System.out.println("Case #" + t + "\n" + res); } scanner.close(); } }