ZJU 3531 Alice Madness Return 【BFS HASH状态】

有一段日子木有更新solution神马的,北京区域赛的准备工作好烦哪。强烈要求出现一个组委会,而不是我们这帮集训队的来干各种奇葩活。

言归正传,9月的浙大月赛可搞题颇多,场上就想写这题,可惜木有机时,只能场下写咯。可惜一写就掉坑里了,直到现在才爬出来,好恶心的一道题啊。

题意:
10*10的棋盘,有一个你控制的棋子A,每步可四向移动;有一个镜像棋子B,和你呈镜像运动,遇边、石则当前回合不动;路上有石头,不可入;有压路机,循环运动,遇神杀神,遇石回头;地图上有<=5个宝石,你需要用A去拾取全部(WA点1,用A拾取,B没用);有两个出口,需要让A、B同时到达这俩出口,且拿满宝石,则你赢了。被压路机压到A、B或者同时到达出口时宝石没拿满,都是死。

做法:
就是BFS+模拟,模拟的规则略复杂。
先说状态,压路机方向 + 压路机位置 + A位置 + B位置 + 五块宝石的拿取状态。最后一个状态我用2^5来存,所以整体是一个9位数(虽说大牛们说前两个状态因为压路机的循环移动性质乘起来只有20种)。整体状态数=2 * 10 * 100 * 100 * 32 = 6400000 ,果断hash。一开始用MAP,TLE了;后来只能手写hash了,不仅要记hash之前的状态值还需要记对应状态的权值,难怪那么大内存。
接着就是模拟了:
每次解hash(注意hash数字时候的顺序)得取当前状态,然后算出下一回合A、B、压路机K的位置和宝石状态。
但是判定非法的时候,需要按顺序判断:
因为走的顺序是A、B、K,所以先判断A,check(超范围、碰R),碰K(未动),碰B,碰到则状态非法;再判断B,若碰新A,check,碰K,则不动。先不判K。
然后判断A是否拿到了新的宝石。
此时要判断A、B是否达到了出口,如果达到了而宝石不齐,则状态非法(wa点2);若齐了,则更新最短路长(不要在出队以后再更新,要在入队前更新,否则压路机会把这种情况给判非法掉)。只要达到出口,则状态不进队。
最后判K,吃了A或者B则状态非法。(WA点3)

代码写的好矬啊,别人800ms过,我wa+tle了两版才2400ms过。。。蒟蒻伤不起啊。

#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<map>
#include 
<queue>
#include 
<algorithm>
using namespace std;
#define maxn 11
#define hashsize (6400013)
#define maxm (hashsize + 10)
int ans;
const int inf = 1 << 30;
char mst[maxn][maxn];
int vis[maxm];
int cas;
int tot;
struct HASH
{
    
int x,step;
    HASH(){}
    HASH(
int _x,int _s):x(_x),step(_s){}
}h[maxm];
inline 
int find(int x)
{
    
int z = x % hashsize;
    
return vis[z] == cas?h[z].step:-1;
}
inline 
void insert(int x,int value)
{
    
int z = x % hashsize;
    vis[z] 
= cas;
    h[z] 
= HASH(x,value);
}
inline 
void update(int x,int value)
{
    
int z = x % hashsize;
    h[z].step 
= value;
}
struct node
{
    
int x,y;
    node(){}
    node(
int a,int b):x(a),y(b){}
    
bool operator ==(const node p)
    {
        
return x == p.x && y == p.y;
    }
}pa,pb,en[
2],ki,pc[6];
int r,c;
int pcs;
char dir;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
char rd[] = {'N','S','W','E'};
int co(char _d)
{
    
for(int i = 0;i < 4;i++)
        
if(rd[i] == _d)
            
return i;
}
int hash(int _d,node p[],bool gd[])
{
    
int x = 0;
    
for(int i = 0;i < pcs;i++)
        
if(gd[i])
            x 
|= (1 << i);
    
int idx = 100;
    
for(int i = 2;i >= 0;i--)
    {
        x 
+= idx * p[i].x;
        idx 
*= 10;
        x 
+= idx * p[i].y;
        idx 
*= 10;
    }
    x 
+= (_d + 1* idx;
    
return x;
}
inline 
bool check(int x,int y)
{
    
return 0 <= x && x < r && 0 <= y && y < c && mst[x][y] != 'R';
}
void bfs()
{
    queue 
<int> Q;
    
bool gd[6];
    
for(int i = 0;i < pcs;i++)
        gd[i] 
= true;
    node p[
3];
    p[
0= ki;
    p[
1= pa;
    p[
2= pb;
    
int s = hash(co(dir),p,gd);
    
//cout << s << endl;
    if(find(s) == -1)
        insert(s,
0);
    Q.push(s);
    
//cout << s << endl;
    while(!Q.empty())
    {
        
int now = Q.front();
        Q.pop();
        
//cout << now << endl;
        int step = find(now);
        
int idx = 100000000;
        
int tdir = now / idx - 1;
        now 
-= (tdir+1* idx;
        idx 
/= 10;
        
//cout << now << endl;
        for(int i = 0;i < 3;i++)
        {
            p[i].y 
= now / idx;
            now 
-= p[i].y * idx;
            idx 
/= 10;
            p[i].x 
= now / idx;
            now 
-= p[i].x * idx;
            idx 
/= 10;
        }
        
//cout << now << endl;
        int x,y;
        x 
= p[0].x + dx[tdir];
        y 
= p[0].y + dy[tdir];
        
if(!check(x,y))
        {
            x 
= p[0].x;
            y 
= p[0].y;
            tdir 
^= 1;
        }
        node tk 
= node(x,y);
        
for(int i = 0;i < 4;i++)
        {
            
bool dg[6= {0};
            
int ax = p[1].x + dx[i],ay = p[1].y + dy[i];
            
int bx = p[2].x + dx[i^1],by = p[2].y + dy[i^1];
            
if(!check(ax,ay) ||  node(ax,ay) == p[0|| node(ax,ay) == p[2])//they can stay in the same point???
                continue;
            
if(!check(bx,by) || node(bx,by) == p[0|| node(bx,by) == node(ax,ay))
            {
                bx 
= p[2].x;
                by 
= p[2].y;
            }
            
int what = 0;
            
for(int j = 0;j < pcs;j++)
                
if(((now >> j) & 1&& !(node(ax,ay) == pc[j]))
                {    
                    dg[j] 
= 1;
                    what 
|= 1 << j;
                }
            node q[
3];
            q[
0= tk;
            q[
1= node(ax,ay);
            q[
2= node(bx,by);
            
int ano = step + 1;
            
if((en[0== q[1&& en[1== q[2]) || (en[0== q[2&& en[1== q[1]))
            {
                
if(what == 0)
                    ans 
= min(ano,ans);
                
else
                    
continue;
            }
            
if(q[0== q[1|| q[0== q[2])
                
continue;
            
int temp = hash(tdir,q,dg);
            
int comp = find(temp);
            
if(comp == -1 || comp > ano)
            {
                
if(comp == -1)
                    insert(temp,ano);
                
else
                    update(temp,ano);
                Q.push(temp);
            }
        }
    }
    printf(
"%d\n",ans == inf?-1:ans);
}
int main()
{
    cas 
= 0;
    
while(scanf("%d %d",&r,&c) == 2)
    {
        cas
++;
        
int end = 0;
        pcs 
= 0;
        tot 
= 0;
        
for(int i = 0;i < r;i++)
            
for(int j = 0;j < c;j++)
            {
                
char opt;
                scanf(
" %c",&opt);
                mst[i][j] 
= opt;
                
switch(opt)
                {
                    
case 'A':
                        pa 
= node(i,j);
                        
break;
                    
case 'B':
                        pb 
= node(i,j);
                        
break;
                    
case 'K':
                        ki 
= node(i,j);
                        
break;
                    
case 'E':
                        en[end
++= node(i,j);
                        
break;
                    
case 'M':
                        pc[pcs
++= node(i,j);
                        
break;
                }
            }
        ans 
= inf;
        scanf(
" %c",&dir);
        bfs();
    }
}

posted on 2011-09-21 21:36 BUPT-[aswmtjdsj] @ Penalty 阅读(231) 评论(0)  编辑 收藏 引用 所属分类: ZOJ Solution Report搜索


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜