Untitled

package Bai1;

import java.util.Scanner;

public class ShipperHugo {
	static int sx, sy, hx ,hy;
	static int[][] adj = new int[15][15];
	static int n;							// n la so dia diem tong cong
	static Tile[] pos = new Tile[15];
	static int[] visit = new int[15];
	static int min, sum, count	;
	
	static int abs(int x){
		
		return x < 0 ? -x:x;
	}
	
	static int dis(Tile x, Tile y){
		return abs(y.x - x.x) + abs(y.y - x.y);
	}
	
	static void backtrack(int i){
		if(sum > min)	return;
		if (count == n){
			min = sum < min ? sum : min;
			return;
		}
		for (int j = 0; j < n; j++){
			if (count < n - 1){
				if (j == n - 1)	continue;
				if (visit[j] == 0){
					//System.out.println("Visit " + j + " with distance " + adj[i][j]);
					visit[j] = 1;
					sum += adj[i][j];
					count++;
					backtrack(j);
					visit[j]= 0;
					sum -= adj[i][j];
					count--;
				}
			}
			else if (count == n - 1){
				if (visit[j] == 0){
					visit[j] = 1;
					sum += adj[i][j];
					count++;
					backtrack(j);
					visit[j]= 0;
					sum -= adj[i][j];
					count--;
				}
			}
		}
		return;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++){
			sum = 0; 
			count = 1;
			min = 999999;
			sx = sc.nextInt();
			sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();
			n = sc.nextInt();
			
			pos[0] = new Tile(sx, sy);
			int id = 1;
			for (int i = 0; i < n; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				pos[id] = new Tile(x, y);
				id++;
			}
			pos[id] = new Tile(hx, hy);
			id = id + 1;
			n = id;
			for (int i = 0; i < id - 1; i++){
				for (int j = i + 1; j < id; j++){
					int distance = dis(pos[i], pos[j]);
					adj[i][j] = distance;
					adj[j][i] = distance;
				}
			}
//			for (int i = 0; i < id; i++){
//				for (int j = 0; j < id; j++){
//					System.out.print(adj[i][j] + " ");
//				}
//				System.out.println();
//			}
			//System.out.println();
			visit[0] = 1;
			backtrack(0);
			System.out.println("Case #" + tc + " " + min);
		}
	}

}