【HDOJ】1401 Solitaire

双向BFS+状态压缩。
  1 /* 1401 */
  2 #include <iostream>
  3 #include <queue>
  4 #include <map>
  5 #include <algorithm>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cstdlib>
  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<int, int> 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<Node_t> 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_JUDGE
142         freopen("data.in", "r", stdin);
143         freopen("data.out", "w", stdout);
144     #endif
145     
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         else
157             puts("NO");
158     }
159     
160     return 0;
161 }