Untitled

package Lesson_15;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Hugo_Giao_Hang {
	static int T, Sx, Sy, Hx, Hy;
	static int N, start[], end[], distance[][];
	static int cr, cc, nr, nc, D, sum, min;
	static boolean visited[];
	
	public static class Queue{
		static int front, rear;
		static int Data[];
		
		public Queue() {
			this.front = this.rear = -1;
			Data = new int[1000];
		}
		
		public static void reset(){
			front = rear = -1;
		}
		
		public static void enQueue(int value){
			Data[++rear] = value;
		}
		
		public static int deQueue(){
			return Data[++front];
		}
		
		public static boolean is_Empty(){
			return front == rear;
		}
	}
	
	public static void backTrack(int index, int row){
		if(sum >= min) return;
		if(index == N+1){
			 sum += distance[row][N+1];
			 if(sum < min) min = sum;
			 sum -= distance[row][N+1];
			 return;
		}
		for(int i = 1; i <= N; i++){
			if(distance[row][i] != 0 && !visited[i]){
				sum += distance[row][i];
				visited[i] = true;
				backTrack(index+1, i);
				visited[i] = false;
				sum -= distance[row][i];
			}
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Hugo_GiaoHang"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			Sx = scanner.nextInt();
			Sy = scanner.nextInt();
			Hx = scanner.nextInt();
			Hy = scanner.nextInt();
			N = scanner.nextInt();
			start = new int[N+2];
			end = new int[N+2];
			start[0] = Sx; end[0] = Sy;
			start[N+1] = Hx; end[N+1] = Hy;
			for(int i = 1; i <= N; i++){
				start[i] = scanner.nextInt();
				end[i] = scanner.nextInt();
			}
			
			Queue rQueue = new Queue();
			Queue cQueue = new Queue();
			
			
			distance = new int[12][12];
			visited = new boolean[12];
			for(int i = 0; i <= N + 1; i++ ){
				rQueue.enQueue(start[i]);
				cQueue.enQueue(end[i]);
				while(!rQueue.is_Empty()){
					cr = rQueue.deQueue();
					cc = cQueue.deQueue();
					for(int j = 0; j <= N+1; j++){
						if(cr == start[j] && cc == end[j]){
							distance[i][j] = 0;
							continue;
						}
						else{
							D = Math.abs(start[j] - cr) + Math.abs(end[j] - cc);
							distance[i][j] = D;
						}
					}
				}
			}
			for(int i = 0; i <= N+1; i++){
				for(int j = 0; j <= N+1; j++){
					System.out.print(distance[i][j] + " ");
				}
				System.out.println();
			}
			
			min = 10000000;
			backTrack(1, 0);
			System.out.println("Case #" + tc + " " + min);
		}
	}

}