Untitled
unknown
plain_text
18 days ago
2.0 kB
2
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int sx, sy, hx, hy, n, count, min, dis; static int[][] A, dist; static int[] visit; public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub System.setIn(new FileInputStream("src/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { sx = sc.nextInt(); sy = sc.nextInt(); hx = sc.nextInt(); hy = sc.nextInt(); n = sc.nextInt(); A = new int[n + 2][2]; int x, y; count = 1; for (int i = 0; i < n; i++) { x = sc.nextInt(); y = sc.nextInt(); A[count][0] = x; A[count][1] = y; count++; } A[0][0] = sx; A[0][1] = sy; A[count][0] = hx; A[count][1] = hy; count++; dist = new int[count][count]; visit = new int[count]; for (int i = 0; i < count; i++) { getDistance(i); } min = Integer.MAX_VALUE; dis = 0; ship(0, 1); System.out.println("Case #" + tc + " " + min); } sc.close(); } private static void ship(int idx, int k) { // TODO Auto-generated method stub if(dis>=min) return; if (k == count - 1) { dis += dist[idx][count-1]; min = dis < min ? dis : min; dis -= dist[idx][count-1]; return; } visit[idx] = 1; for (int i = 1; i < count-1; i++) { if(visit[i]==0) { dis+= dist[idx][i]; ship(i, k+1); dis-= dist[idx][i]; } } visit[idx] = 0; } private static void getDistance(int idx) { // TODO Auto-generated method stub int r1, c1, dis; r1 = A[idx][0]; c1 = A[idx][1]; for (int i = 0; i < n + 2; i++) { if (i != idx) { int r2 = A[i][0]; int c2 = A[i][1]; r2 = r1 > r2 ? r1 - r2 : r2 - r1; c2 = c1 > c2 ? c1 - c2 : c2 - c1; dis = r2 + c2; dist[idx][i] = dis; } } } }
Leave a Comment