ZOJ 1505 Solitaire

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    {01}10}- 10}{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}

posted on 2008-02-26 14:20 杜仲当归 阅读(428) 评论(1)  编辑 收藏 引用 所属分类: 搜索剪枝

评论

# re: ZOJ 1505 Solitaire 2008-05-08 00:08 x

我想问一下,在每个bfs中,在第一次overlap ( tp, i ) 失败后会执行
tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];

在执行完这句后应该还需要一次overlap ( tp, i )判断吧?因为跳过一个子可能还有一个子这样两个字就重合了,如果数据变态一点的话,maybe wa?。

是不是应该这样写:
if ( overlap ( tp, i ) )
tp.g[i].x += dir[j][0], tp.g[i].y += dir[j][1];
if ( !check ( tp.g[i].x, tp.g[i].y ) )
continue;
if ( overlap ( tp, i ) )
continue;
  回复  更多评论   

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜