Untitled
plain_text
a month ago
3.2 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; static int[] c; static int[] p; static int[] tham; static int[] res; static int[] visit; static int[] mt; static int[] d = {-1,1}; static int min; static int[] temp; public static void main(String[] args) throws FileNotFoundException{ System.setIn(new FileInputStream("src/Hugo_Di_Tau/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int test_case = 1; test_case <= T; test_case++){ n = sc.nextInt(); c = new int[3]; p = new int[3]; tham = new int[3]; res = new int[3]; visit = new int[n+1]; mt = new int[n+1]; temp = new int[n+1]; for(int i = 0; i < 3; i++){ c[i] = sc.nextInt(); p[i] = sc.nextInt(); } min = 100007; Try(0); //Trai(0); //Trai(1); //Trai(2); /*for(int i1 = 1; i1 <= n; i1++){ System.out.print(mt[i1] + " "); }*/ System.out.println("Case #" + test_case); System.out.println(min); } } public static void Trai(int k){ int u = c[k]; int v = p[k]; int m = 0; if(visit[u] == 0){ visit[u] = 1; mt[u] = 1; m++; } if(m < v){ for(int i = 1; i <= n; i++){ if(u-i >= 1 && u-i <= n && visit[u-i] == 0){ visit[u-i] = 1; mt[u-i] = Math.abs(i)+1; m++; } if(m == v){ break; } if(u+i >= 1 && u+i <= n && visit[u+i] == 0){ visit[u+i] = 1; mt[u+i] = Math.abs(i)+1; m++; } if(m == v){ break; } } } } public static void Phai(int k){ int u = c[k]; int v = p[k]; int m = 0; if(visit[u] == 0){ visit[u] = 1; mt[u] = 1; m++; } if(m < v){ for(int i = 1; i <= n; i++){ if(u+i >= 1 && u+i <= n && visit[u+i] == 0){ visit[u+i] = 1; mt[u+i] = Math.abs(i)+1; m++; } if(m == v){ break; } if(u-i >= 1 && u-i <= n && visit[u-i] == 0){ visit[u-i] = 1; mt[u-i] = Math.abs(i)+1; m++; } if(m == v){ break; } } } } public static void update(){ for(int i = 1; i <= n; i++){ mt[i] = 0; visit[i] = 0; } } public static void BTrack(int k){ if(k == 3){ for(int i = 0; i < 3; i++){ if(temp[i] == 0){ Trai(res[i]); }else if(temp[i] == 1){ Phai(res[i]); } //System.out.println(temp[i]); /*for(int i1 = 1; i1 <= n; i1++){ System.out.print(mt[i1] + " "); } System.out.println();*/ } int tong = 0; for(int i = 1; i <= n; i++){ tong += mt[i]; } if(tong < min){ min = tong; } update(); //System.out.println(tong); }else{ for(int i = 0; i < 2; i++){ temp[k] = i; BTrack(k+1); temp[k] = 0; } } } public static void Try(int k){ if(k == 3){ BTrack(0); return; }else{ for(int i = 0; i < 3; i++){ if(tham[i] == 0){ res[k] = i; tham[i] = 1; Try(k+1); tham[i] = 0; } } } } }