-
Notifications
You must be signed in to change notification settings - Fork 0
/
BJ12908.java
47 lines (39 loc) · 1.47 KB
/
BJ12908.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package BJ;
import java.io.*;
import java.util.*;
public class BJ12908 {
static long tp[][],xe,ye,ans=Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long xs = Long.parseLong(st.nextToken());
long ys = Long.parseLong(st.nextToken());
st = new StringTokenizer(br.readLine());
xe = Long.parseLong(st.nextToken());
ye = Long.parseLong(st.nextToken());
tp = new long[3][4];
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++) {
tp[i][j] = Long.parseLong(st.nextToken());;
}
}
DFS(0,xs,ys,0);
System.out.print(ans);
}
static void DFS(int depth, long x, long y, long value){
if (value>ans) return;
if (depth==4) ans = Math.min(ans, value+Math.abs(xe-x)+Math.abs(ye-y));
else{
for (int i = 0; i < 3; i++) {
long nV = value+Math.abs(tp[i][0]-x)+Math.abs(tp[i][1]-y)+10;
DFS(depth+1, tp[i][2], tp[i][3], nV);
}
for (int i = 0; i < 3; i++) {
long nV = value+Math.abs(tp[i][2]-x)+Math.abs(tp[i][3]-y)+10;
DFS(depth+1, tp[i][0], tp[i][1], nV);
}
DFS(depth+1, x,y,value);
}
}
}