本文共 2894 字，大约阅读时间需要 9 分钟。
双向BFS+状态压缩。
1 /* 1401 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 11 struct Point_t{ 12 char x, y; 13 friend bool operator ==(const Point_t &a, const Point_t &b) { 14 return a.x==b.x && a.y==b.y; 15 } 16 }; 17 18 typedef struct Node_t { 19 Point_t p[4]; 20 int t; 21 } Node_t; 22 23 const char n = 8; 24 Node_t b1, b2; 25 map tb; 26 char dir[4][2] = { 27 -1,0,1,0,0,-1,0,1 28 }; 29 30 bool comp(const Point_t &a, const Point_t &b) { 31 if (a.x == b.x) 32 return a.y < b.y; 33 return a.x < b.x; 34 } 35 36 int calHash(Node_t nd) { 37 int ret = 0; 38 int i, j; 39 40 for (i=0,j=0; i<4; ++i,j+=6) { 41 ret |= (nd.p[i].x << j); 42 ret |= (nd.p[i].y << (j+3)); 43 } 44 return ret; 45 } 46 47 bool judge(Node_t &nd, int v, int d) { 48 int i, j, k; 49 50 nd.p[v].x += dir[d][0]; 51 nd.p[v].y += dir[d][1]; 52 53 if (nd.p[v].x<=0 || nd.p[v].x>n || nd.p[v].y<=0 || nd.p[v].y>n) 54 return false; 55 56 for (i=0; i<4; ++i) { 57 if (i != v) { 58 if (nd.p[i] == nd.p[v]) { 59 // jump over one piece 60 nd.p[v].x += dir[d][0]; 61 nd.p[v].y += dir[d][1]; 62 if (nd.p[v].x<=0 || nd.p[v].x>n || nd.p[v].y<=0 || nd.p[v].y>n) 63 return false; 64 for (j=0; j<4; ++j) 65 if (j!=v && nd.p[j]==nd.p[v]) 66 return false; 67 break; 68 } 69 } 70 } 71 72 sort(nd.p, nd.p+4, comp); 73 return true; 74 } 75 76 int bfs() { 77 int i, j, k; 78 queue Q1, Q2; 79 Node_t nd, tmp; 80 81 sort(b1.p, b1.p+4, comp); 82 sort(b2.p, b2.p+4, comp); 83 Q1.push(b1); 84 Q2.push(b2); 85 tb[calHash(b1)] = 1; 86 tb[calHash(b2)] = 2; 87 88 while (!Q1.empty() || !Q2.empty()) { 89 if (!Q1.empty()) { 90 nd = Q1.front(); 91 Q1.pop(); 92 if (nd.t < 4) { 93 tmp = nd; 94 ++tmp.t; 95 for (i=0; i<4; ++i) { 96 for (j=0; j<4; ++j) { 97 nd = tmp; 98 if (judge(nd, i, j)) { 99 k = calHash(nd);100 if (tb[k] == 2)101 return 1;102 if (tb[k] != 1) {103 Q1.push(nd);104 tb[k] = 1;105 }106 }107 }108 }109 }110 }111 if (!Q2.empty()) {112 nd = Q2.front();113 Q2.pop();114 if (nd.t < 4) {115 tmp = nd;116 ++tmp.t;117 for (i=0; i<4; ++i) {118 for (j=0; j<4; ++j) {119 nd = tmp;120 if (judge(nd, i, j)) {121 k = calHash(nd);122 if (tb[k] == 1)123 return 1;124 if (tb[k] != 2) {125 Q2.push(nd);126 tb[k] = 2;127 }128 }129 }130 }131 }132 }133 }134 135 return 0;136 }137 138 int main() {139 int i, j, k;140 141 #ifndef ONLINE_JUDGE142 freopen("data.in", "r", stdin);143 freopen("data.out", "w", stdout);144 #endif145 146 b1.t = b2.t = 0;147 while (scanf("%d %d", &b1.p[0].x, &b1.p[0].y) != EOF) {148 for (i=1; i<4; ++i)149 scanf("%d %d", &b1.p[i].x, &b1.p[i].y);150 for (i=0; i<4; ++i)151 scanf("%d %d", &b2.p[i].x, &b2.p[i].y);152 tb.clear();153 k = bfs();154 if (k)155 puts("YES");156 else157 puts("NO");158 }159 160 return 0;161 }
转载于:https://www.cnblogs.com/bombe1013/p/4296589.html