Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
1.4 kB
2
Indexable
Never
package Test;
import java.util.Scanner;

import java.io.FileInputStream;
public class Solution {
	static int sx, sy, hx, hy, n, min, sum, cnt;
	static int[] arrx;
	static int[] arry;
	static boolean[] visited;
	static void backtrack(int index, int cnt, int sum) {
		if(cnt < n + 1 && visited[n+1] == true) {
			return;
		}
		if(cnt == n + 1) {
			if(sum < min) {
				min = sum;
			}
			return;
		}
		for(int i = 1 ; i < n + 2; i++) {
			if(visited[i] == false) {
				visited[i] = true; 
				backtrack(i, cnt + 1,sum + Math.abs(arrx[index] - arrx[i]) + Math.abs(arry[index] - arry[i]));
				visited[i] = false; 
				
			}
		}
	}
	public static void main(String[] agr) throws Exception{
		System.setIn(new FileInputStream("Text")); 
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			sx = sc.nextInt();
			sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();
			n = sc.nextInt();
			arrx = new int[n + 2];
			arry = new int[n + 2];
			arrx[0] = sx;
			arry[0] = sy;
			for(int i = 1; i < n+1; i++) {
				arrx[i] = sc.nextInt();
				arry[i] = sc.nextInt();
			}
			arrx[n+1] = hx;
			arry[n+1] = hy;
			visited = new boolean[n + 2];
			min = Integer.MAX_VALUE;
			sum = 0;
			cnt = 0;
			backtrack(0, 0, 0);
			System.out.println("Case #" + Case + " " + min);
			
		}
		
	}
}
Leave a Comment