| 2761550 |
2008-02-26 14:10:05 |
Accepted
|
1505
|
C++ |
00:00.11 |
3480K |
C.D.=.=
|
真没想到能这么快。不过总算是完全自己写的一道题，尽管还有不少地方可以加强。
起初打算使用单边BFS+hash，这样时间可以更省，然而空间不够。于是上网搜了一下，看到有人用双向BFS+位运算达到0s，大愕。遗憾的是没有代码。自力更生吧。
这里用了最小白的双向BFS，一边搜完继续搜另一边；还用到了STL，我越来越懒了。应该想想怎样把搜索策略提高一些，比如一层节点搜完之后的转向。
1
#include <cstdio>
2#include <string>
3#include <set>
4#include <algorithm>
5using namespace std;
6
7#define check(i,j) ( i < 8 && i >= 0 && j < 8 && j >= 0 )
8
9typedef struct
10
{
11
int x, y;
12
} Grid;
13
14typedef struct
15{
16 Grid g[4];
17 int step;
18} Point;
19
20Point q[70000], a, b; //搜索队列中存放代表坐标的八个数字
21set <int> ia, ib;
22int dir[4][2] =
23{
24
{0, 1}, { 1, 0}, { - 1, 0}, {0, -1 }
25};
26
27int cmp ( const Grid &a, const Grid &b )
28{
29 return a.x < b.x || a.x == b.x && a.y < b.y;
30}
31
32int init ();
33int bfs ();
34int hash ( const Point & );
35int overlap ( const Point &, int );
36
37int main ()
38{
39 //freopen ( "in.txt", "r", stdin );
40 //test ();
41 while ( init () )
42 {
43 if ( bfs () )
44 printf ( "YES\n" );
45 else
46 printf ( "NO\n" );
47
}
48 return 0;
49}
50
51int init ()
52{
53 int i;
54 for ( i = 0; i < 4; i ++ )
55 {
56 if ( scanf ( "%d%d", &a.g[i].x, &a.g[i].y ) != 2 )
57 return 0;
58 a.g[i].x --, a.g[i].y --, a.step = 0;
59 }
60 sort ( a.g, a.g + 4, cmp );
61 for ( i = 0; i < 4; i ++ )
62 {
63 scanf ( "%d%d", &b.g[i].x, &b.g[i].y );
64 b.g[i].x --, b.g[i].y --, b.step = 0;
65 }
66 sort ( b.g, b.g + 4, cmp );
67 ia.clear ();
68 ib.clear ();
69 ia.insert ( hash ( a ) );
70 ib.insert ( hash ( b ) );
71 return 1;
72}
73
74int bfs ()
75{
76 int st, ed, i, j, thash, hashb = hash ( b ), hasha = hash ( a );
77 q[0].step = 0;
78 memcpy ( q[0].g, a.g, sizeof ( a.g ) );
79 //搜索A队列，存hash
80 for ( st = -1, ed = 0; st ++ < ed; )
81 {
82 Point tp;
83 tp.step = q[st].step + 1;
84 if ( tp.step == 5 )
85 continue;
86 for ( i = 0; i < 4; i ++ )
87 {
88 for ( j = 0; j < 4; j ++ )
89 {
90 memcpy ( tp.g, q[st].g, sizeof ( tp.g ) );
91 tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];
92 if ( !check ( tp.g[i].x, tp.g[i].y ) )
93 continue;
94 if ( overlap ( tp, i ) )
95 tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];
96 if ( !check ( tp.g[i].x, tp.g[i].y ) )
97 continue;
98 sort ( tp.g, tp.g + 4, cmp );
99 thash = hash ( tp );
100 if ( ia.find ( thash ) == ia.end () )
101 {
102 ia.insert ( thash );
103 memcpy ( q[++ ed].g, tp.g, sizeof ( tp.g ) );
104 q[ed].step = tp.step;
105 }
106 }
107 }
108 }
109 //pt ( ed );
110 //搜索B队列，看是否和A队列里某一hash值重合
111 q[0].step = 0;
112 memcpy ( q[0].g, b.g, sizeof ( b.g ) );
113 for ( st = -1, ed = 0; st ++ < ed; )
114 {
115 if ( ia.find ( hash ( q[st] ) ) != ia.end () )
116 return 1;
117 Point tp;
118 tp.step = q[st].step + 1;
119 if ( tp.step == 5 )
120 continue;
121 for ( i = 0; i < 4; i ++ )
122 {
123 for ( j = 0; j < 4; j ++ )
124 {
125 memcpy ( tp.g, q[st].g, sizeof ( tp.g ) );
126 tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];
127 if ( !check ( tp.g[i].x, tp.g[i].y ) )
128 continue;
129 if ( overlap ( tp, i ) )
130 tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];
131 if ( !check ( tp.g[i].x, tp.g[i].y ) )
132 continue;
133 sort ( tp.g, tp.g + 4, cmp );
134 thash = hash ( tp );
135 if ( ib.find ( thash ) == ib.end () )
136 {
137 ib.insert ( thash );
138 memcpy ( q[++ ed].g, tp.g, sizeof ( tp.g ) );
139 q[ed].step = tp.step;
140 }
141 }
142 }
143 }
144 //lookfor ();
145 return 0;
146}
147
148int hash ( const Point &p )
149{
150 //八个数依次×8
151 //sort ( p.g, p.g + 4, cmp );
152 int sum = 0;
153 for ( int i = 0; i < 4; i ++ )
154 {
155 sum *= 8;
156 sum += p.g[i].x;
157 sum *= 8;
158 sum += p.g[i].y;
159 }
160 return sum;
161}
162
163int overlap ( const Point &p, int id )
164{
165 //判重叠
166 int i;
167 for ( i = 0; i < 4; i ++ )
168 {
169 if ( i == id )
170 continue;
171 if ( p.g[i].x == p.g[id].x && p.g[i].y == p.g[id].y )
172 return 1;
173 }
174 return 0;
175}