# Untitled

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);

}

}
}
```