[POJ 1324] | Eurce's Blog

搜索 + 滚动hash

给出最大20*20的格盘，和一条长为l的蛇，目的是使蛇头移动到(1,1)。格盘中存在k个格子是无法通过的石头，蛇也不能碰到自己的身体，包括最尾的一格。若能到(1,1)，输出最短距离，否则输出-1。

考虑保存蛇的状态时，只保存其蛇头位置，以及指向之前蛇头的指针。由此就能搜索处理蛇的移动方案。考虑判重时，使用滚动hash，即到一个新状态时，将之前蛇头对应的hash值升位并减去之前蛇尾的部分，再加上新的蛇头值即可。

另外就是，可以考虑优先向(1,1)的方向移动，以及搜索之前先判断蛇头是否可达(1,1)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define HM 100003
#define HC 31
#define QL 100000
#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;
int mv[4][2]={-1,0,0,-1,1,0,0,1};
char s[20][20];
int q[QL],qh,qt;

struct H
{
    int x,y,d,p,u;
}h[MEM];

struct E
{
    int v,p;
}e[MEM];

inline void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

inline bool chke()
{
    int i,j,k,l;
    for(l=hd[h[hl].u];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)
            if(h[j].x!=h[k].x||h[j].y!=h[k].y)
                break;
        if(i==pl)
            return 0;
    }
    return 1;
}

inline bool chk(int i,int j)
{
    if(i<0||i>=n||j<0||j>=m)
        return 0;
    if(s[i][j])
        return 0;
    return 1;
}

bool prechk()
{
    int i,j,k,l,x,y;
    char ss[20][20];
    memcpy(ss,s,sizeof ss);
    qh=qt=0;
    q[qh++]=0;
    s[0][0]=1;
    while(qt!=qh)
    {
        i=q[qt++];
        j=i/20;
        k=i%20;
        for(l=0;l<4;l++)
        {
            x=j+mv[l][0];
            y=k+mv[l][1];
            if(chk(x,y))
            {
                s[x][y]=1;
                q[qh++]=x*20+y;
            }
        }
    }
    i=s[h[0].x][h[0].y];
    memcpy(s,ss,sizeof ss);
    return i;
}

int bfs()
{
    int i,j,k,l,x,y;
    if(h[0].x==0&&h[0].y==0)
        return 0;
    q[qh++]=0;
    while(qt!=qh)
    {
        i=q[qt++];
        if(qt==QL)
            qt=0;
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=1;
        for(l=0;l<4;l++)
        {
            x=h[i].x+mv[l][0];
            y=h[i].y+mv[l][1];
            if(chk(x,y))
            {
                if(x==0&&y==0)
                    return h[i].d+1;
                h[hl].x=x;
                h[hl].y=y;
                h[hl].d=h[i].d+1;
                h[hl].p=i;
                for(j=1,k=i;j<pl;j++,k=h[k].p);
                h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y
                        +HC*x+y)%HM;
                if(h[hl].u<0)
                    h[hl].u+=HM;
                if(chke())
                {
                    adde(h[hl].u,hl);
                    q[qh++]=hl++;
                    if(qh==QL)
                        qh=0;
                }
            }
        }
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=0;
    }
    return -1;
}

void init()
{
    int i,j,k,l;
    hl=el=0;
    qh=qt=0;
    memset(s,0,sizeof s);
    memset(hd,-1,sizeof hd);
    for(i=0,mmy=1;i<pl*2;i++)
        mmy=(mmy*HC)%HM;
    mmx=mmy*HC%HM;
    for(hl=0;hl<pl;hl++)
    {
        scanf("%d%d",&j,&k);
        h[hl].x=j-1;
        h[hl].y=k-1;
        h[hl].p=hl+1;
    }
    h[0].d=0;
    for(i=pl-1,j=0;i>-1;i--)
    {
        j=(j*HC+h[i].x)%HM;
        j=(j*HC+h[i].y)%HM;
    }
    h[0].u=j;
    adde(j,0);
    scanf("%d",&l);
    while(l--)
    {
        scanf("%d%d",&i,&j);
        s[i-1][j-1]=1;
    }
}

void solve()
{
    if(!prechk())
        printf("Case %d: -1\n",++t);
    else
        printf("Case %d: %d\n",++t,bfs());
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&pl)&&n)
    {
        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

169

170

171

172

173

174

175

176

177

178

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define HM 100003

#define HC 31

#define QL 100000

#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;

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

char s[20][20];

int q[QL],qh,qt;

struct H

{

int x,y,d,p,u;

}h[MEM];

struct E

{

int v,p;

}e[MEM];

inline void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

inline bool chke()

{

int i,j,k,l;

for(l=hd[h[hl].u];l!=-1;l=e[l].p)

{

j=e[l].v;

for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)

if(h[j].x!=h[k].x||h[j].y!=h[k].y)

break;

if(i==pl)

return 0;

}

return 1;

}

inline bool chk(int i,int j)

{

if(i<0||i>=n||j<0||j>=m)

return 0;

if(s[i][j])

return 0;

return 1;

}

bool prechk()

{

int i,j,k,l,x,y;

char ss[20][20];

memcpy(ss,s,sizeof ss);

qh=qt=0;

q[qh++]=0;

s[0][0]=1;

while(qt!=qh)

{

i=q[qt++];

j=i/20;

k=i%20;

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

{

x=j+mv[l][0];

y=k+mv[l][1];

if(chk(x,y))

{

s[x][y]=1;

q[qh++]=x*20+y;

}

i=s[h[0].x][h[0].y];

memcpy(s,ss,sizeof ss);

return i;

}

int bfs()

{

int i,j,k,l,x,y;

if(h[0].x==0&&h[0].y==0)

return 0;

q[qh++]=0;

while(qt!=qh)

{

i=q[qt++];

if(qt==QL)

qt=0;

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=1;

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

{

x=h[i].x+mv[l][0];

y=h[i].y+mv[l][1];

if(chk(x,y))

{

if(x==0&&y==0)

return h[i].d+1;

h[hl].x=x;

h[hl].y=y;

h[hl].d=h[i].d+1;

h[hl].p=i;

for(j=1,k=i;j<pl;j++,k=h[k].p);

h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y

+HC*x+y)%HM;

if(h[hl].u<0)

h[hl].u+=HM;

if(chke())

{

adde(h[hl].u,hl);

q[qh++]=hl++;

if(qh==QL)

qh=0;

}

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=0;

}

return -1;

}

void init()

{

int i,j,k,l;

hl=el=0;

qh=qt=0;

memset(s,0,sizeof s);

memset(hd,-1,sizeof hd);

for(i=0,mmy=1;i<pl*2;i++)

mmy=(mmy*HC)%HM;

mmx=mmy*HC%HM;

for(hl=0;hl<pl;hl++)

{

scanf("%d%d",&j,&k);

h[hl].x=j-1;

h[hl].y=k-1;

h[hl].p=hl+1;

}

h[0].d=0;

for(i=pl-1,j=0;i>-1;i--)

{

j=(j*HC+h[i].x)%HM;

j=(j*HC+h[i].y)%HM;

}

h[0].u=j;

adde(j,0);

scanf("%d",&l);

while(l--)

{

scanf("%d%d",&i,&j);

s[i-1][j-1]=1;

}

void solve()

{

if(!prechk())

printf("Case %d: -1\n",++t);

else

printf("Case %d: %d\n",++t,bfs());

}

int main()

{

while(~scanf("%d%d%d",&n,&m,&pl)&&n)

{

init();

solve();

}

return 0;

}