[POJ 3131] | Eurce's Blog

双向广搜

题意：有9个格子，其中8个格子有立方体。立方体相对的两面颜色相同，分别为红、白、蓝色。若某立方体相邻格为空，则该立方体可以向该方向滚动。给定初始状态，问最少滚动多少次（不大于30），可以使各盘格为指定的颜色。

类似这种搜索题，最关键的还是状态的表达。立方体的姿态可以由顶面和正面的颜色来确定，共有6种。有9个格子，考虑使用每个格子3bit，那么搜索空间的规模就是2^(3*9)，大概是1亿。接下来，考虑如何判重。如果使用一个位来表示一个状态，总共需要的内存大小为2^24bytes，也就16MB，是可行的。直接开一个char c[1<<24]，连hash都省了。由此，可以保证所有的操作全部为位运算。接下来考虑搜索的形式，一般来说双向广搜，两边的深度限制相同时可以最大化降低复杂度，但该题反向搜索时起始状态较多（256个状态），层数不深时规模已经很大。因此，正向搜索深度设为20，反向为10。正向搜索完后如果找到解，则直接输出，否则才执行反向搜索。

#include<cstdio>
#include<cstring>

#define M 500000
#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;
int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];
int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6, 
    3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};
char s[2],c[1<<24],cr[1<<24];

struct E
{
    int x,y,b,d;
}e[M];

inline int getl(int x,int y)
{
    return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);
}

void init()
{
    int i,j,k,l;
    eh=el=b=be=0;
    ans=0x7fffffff;
    memset(c,0,sizeof c);
    memset(cr,0,sizeof cr);
    for(i=l=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            b=(b<<3)+5;
            scanf("%s",s);
            be=(be<<3)+t[s[0]];
            if(s[0]=='E')
            {
                xe=j+1;
                ye=i+1;
            }
        }
    }
    b&=~(7<<getl(x,y));
}

inline bool chk(int x,int y,int b,char c[])
{
    return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));
}

inline int calc(int bz,int xz,int yz,int x,int y,int l)
{
    int i,j,k,l1,l2;
    l1=getl(xz,yz); l2=getl(x,y);
    k=mu[(bz&(7<<l2))>>l2][l];
    bz=(bz&~(7<<l2))+(k<<l1);
    return bz;
}

void bfs()
{
    int i,j,k,l;
    e[el].x=x;
    e[el].y=y;
    e[el].b=b;
    e[el].d=0;
    c[e[el].b>>3]|=(1<<(e[el].b&7));
    el++;
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,c))
            {
                c[e[el].b>>3]|=(1<<(e[el].b&7));
                if((e[el].b&bm)==be)
                {
                    ans=e[el].d;
                    return;
                }
                el++;
            }
        }
    }
}

void rbfs()
{
    int i,j,k,l;
    l=1<<(getl(xe,ye)/3);
    eh=el=0;
    for(i=0;i<512;i++)
    {
        if(i&l)
            continue;
        e[el].x=xe;
        e[el].y=ye;
        e[el].b=be;
        e[el].d=0;
        for(j=i,k=0;j;j>>=1,k+=3)
        {
            e[el].b+=(j&1)<<k;
        }
        cr[e[el].b>>3]|=(1<<(e[el].b&7));
        el++;
    }
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==30-D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,cr))
            {
                cr[e[el].b>>3]|=(1<<(e[el].b&7));
                if(!chk(e[el].x,e[el].y,e[el].b,c))
                {
                    ans=e[el].d+D;
                    return;
                }
                el++;
            }
        }
    }
}

void solve()
{
    if((b&bm)==be)
    {
        puts("0");
        return;
    }
    bfs();
    if(ans<0x7fffffff)
    {
        printf("%d\n",ans);
        return;
    }
    rbfs();
    printf("%d\n",ans==0x7fffffff?-1:ans);
}

int main()
{
    t['R']=2; t['W']=4; t['B']=6;
    while(~scanf("%d%d",&x,&y)&&x)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

#include<cstdio>

#include<cstring>

#define M 500000

#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;

int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];

int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6,

3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};

char s[2],c[1<<24],cr[1<<24];

struct E

{

int x,y,b,d;

}e[M];

inline int getl(int x,int y)

{

return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);

}

void init()

{

int i,j,k,l;

eh=el=b=be=0;

ans=0x7fffffff;

memset(c,0,sizeof c);

memset(cr,0,sizeof cr);

for(i=l=0;i<3;i++)

{

for(j=0;j<3;j++)

{

b=(b<<3)+5;

scanf("%s",s);

be=(be<<3)+t[s[0]];

if(s[0]=='E')

{

xe=j+1;

ye=i+1;

}

b&=~(7<<getl(x,y));

}

inline bool chk(int x,int y,int b,char c[])

{

return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));

}

inline int calc(int bz,int xz,int yz,int x,int y,int l)

{

int i,j,k,l1,l2;

l1=getl(xz,yz); l2=getl(x,y);

k=mu[(bz&(7<<l2))>>l2][l];

bz=(bz&~(7<<l2))+(k<<l1);

return bz;

}

void bfs()

{

int i,j,k,l;

e[el].x=x;

e[el].y=y;

e[el].b=b;

e[el].d=0;

c[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

while(eh!=el)

{

i=eh++;

if(e[i].d==D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,c))

{

c[e[el].b>>3]|=(1<<(e[el].b&7));

if((e[el].b&bm)==be)

{

ans=e[el].d;

return;

}

el++;

}

void rbfs()

{

int i,j,k,l;

l=1<<(getl(xe,ye)/3);

eh=el=0;

for(i=0;i<512;i++)

{

if(i&l)

continue;

e[el].x=xe;

e[el].y=ye;

e[el].b=be;

e[el].d=0;

for(j=i,k=0;j;j>>=1,k+=3)

{

e[el].b+=(j&1)<<k;

}

cr[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

}

while(eh!=el)

{

i=eh++;

if(e[i].d==30-D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,cr))

{

cr[e[el].b>>3]|=(1<<(e[el].b&7));

if(!chk(e[el].x,e[el].y,e[el].b,c))

{

ans=e[el].d+D;

return;

}

el++;

}

void solve()

{

if((b&bm)==be)

{

puts("0");

return;

}

bfs();

if(ans<0x7fffffff)

{

printf("%d\n",ans);

return;

}

rbfs();

printf("%d\n",ans==0x7fffffff?-1:ans);

}

int main()

{

t['R']=2; t['W']=4; t['B']=6;

while(~scanf("%d%d",&x,&y)&&x)

{

init();

solve();

}

return 0;

}

虽然没有剪枝，但是内存全部静态分配并且大量使用位运算，程序非常的快（久违的刷到了第一）。