題意：
應(yīng)該是跳棋游戲（我奶奶經(jīng)常在家玩。。），一個8*8棋盤，棋子可以在棋盤上前后左右挪一格或者跳一格（如果相鄰格子有棋子的話），問初始狀態(tài)在8步內(nèi)能否達到給定的終止狀態(tài)。
下限函數(shù)仍然選擇不在位置上的棋子個數(shù)，然后減枝即可。。
話說POJ卡常數(shù)，覺得復雜度應(yīng)該可以了，就是TLE，然后到TOJ上嘗試提交了下，1A，然后只好回來優(yōu)化常數(shù)，把判重換成數(shù)組判重，以6S的時間過了。。哎，JAVA就是可憐啊。。
1 import java.util.*;
2 import java.io.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static point p1[]=new point[4],p2[]=new point[4];
9 static boolean map[][]=new boolean[10][10];
10 static boolean map1[][]=new boolean[10][10];
11 static class point
12 {
13 int r,c;
14 public point(int rr,int cc)
15 {
16 r=rr;
17 c=cc;
18 }
19 public boolean equals(point pos)
20 {
21 return r==pos.r&&c==pos.c;
22 }
23 }
24 static final boolean isnotin(int r,int c,point p[])
25 {
26 for(int i=0;i<4;i++)
27 if(p[i].r==r&&p[i].c==c)
28 return false;
29 return true;
30 }
31 static boolean dfs(point p[],int diff,int layer)
32 {
33 if(layer+diff>8) return false;
34 else if(diff==0)
35 {
36 return true;
37
38 }
39 else
40 {
41 for(int i=0;i<4;i++)
42 {
43 if(p[i].r+1<8&&isnotin(p[i].r+1,p[i].c,p))
44 {
45 p[i].r++;
46 if(dfs(p,diff+(isnotin(p[i].r-1,p[i].c,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
47 {
48
49 return true;
50 }
51 p[i].r--;
52 }
53 if(p[i].c+1<8&&isnotin(p[i].r,p[i].c+1,p))
54 {
55 p[i].c++;
56 if(dfs(p,diff+(isnotin(p[i].r,p[i].c-1,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
57 {
58
59 return true;
60 }
61 p[i].c--;
62 }
63 if(p[i].c-1>=0&&isnotin(p[i].r,p[i].c-1,p))
64 {
65 p[i].c--;
66 if(dfs(p,diff+(isnotin(p[i].r,p[i].c+1,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
67 {
68
69 return true;
70 }
71 p[i].c++;
72 }
73 if(p[i].r-1>=0&&isnotin(p[i].r-1,p[i].c,p))
74 {
75 p[i].r--;
76 if(dfs(p,diff+(isnotin(p[i].r+1,p[i].c,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
77 {
78
79 return true;
80 }
81 p[i].r++;
82 }
83
84 if(p[i].r+2<8&&isnotin(p[i].r+2,p[i].c,p)&&!isnotin(p[i].r+1,p[i].c,p))
85 {
86 p[i].r+=2;
87 if(dfs(p,diff+(isnotin(p[i].r-2,p[i].c,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
88 {
89
90 return true;
91 }
92 p[i].r-=2;
93
94 }
95 if(p[i].c+2<8&&isnotin(p[i].r,p[i].c+2,p)&&!isnotin(p[i].r,p[i].c+1,p))
96 {
97 p[i].c+=2;
98 if(dfs(p,diff+(isnotin(p[i].r,p[i].c-2,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
99 {
100
101 return true;
102 }
103 p[i].c-=2;
104 }
105 if(p[i].c-2>=0&&isnotin(p[i].r,p[i].c-2,p)&&!isnotin(p[i].r,p[i].c-1,p))
106 {
107 p[i].c-=2;
108 if(dfs(p,diff+(isnotin(p[i].r,p[i].c+2,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
109 {
110
111 return true;
112 }
113 p[i].c+=2;
114 }
115 if(p[i].r-2>=0&&isnotin(p[i].r-2,p[i].c,p)&&!isnotin(p[i].r-1,p[i].c,p))
116 {
117 p[i].r-=2;
118 if(dfs(p,diff+(isnotin(p[i].r+2,p[i].c,p2)?0:1)-(map[p[i].r][p[i].c]?1:0),layer+1))
119 {
120
121 return true;
122 }
123 p[i].r+=2;
124 }
125
126
127 }
128 return false;
129 }
130 }
131 public static void main(String[] args) throws IOException{
132 Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
133 for(int i=0;i<4;i++)
134 p1[i]=new point(in.nextInt()-1,in.nextInt()-1);
135 for(int i=0;i<4;i++)
136 p2[i]=new point(in.nextInt()-1,in.nextInt()-1);
137 for(int i=0;i<8;i++)
138 {
139 Arrays.fill(map[i], false);
140 Arrays.fill(map1[i],false);
141 }
142 for(int i=0;i<4;i++)
143 {
144 map[p2[i].r][p2[i].c]=true;
145 map1[p1[i].r][p1[i].c]=true;
146 }
147 int diff=0;
148 for(int i=0;i<4;i++)
149 {
150 boolean flag=false;
151 for(int j=0;j<4&&!flag;j++)
152 if(p1[i].equals(p2[j]))
153 flag=true;
154 if(!flag) diff++;
155 }
156 if(dfs(p1,diff,0)) System.out.println("YES");
157 else System.out.println("NO");
158
159 }
160
161 }
162