Untitled
unknown
plain_text
a year ago
2.7 kB
6
Indexable
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); } } }
Editor is loading...
Leave a Comment