Untitled

mail@pastecode.io avatar
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