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); } } }
Leave a Comment