http://acm.hdu.edu.cn/showproblem.php?pid=1429
典型的状压搜索,在普通的搜索基础上,利用二进制的特性记录钥匙与门, 二进制的每一位代表一把钥匙,比如说拿到了2号钥匙
那么原有的00000变为了00010,当到大了对应的二号门的时候,利用位运算00010来&上1<<2也就是00010就是非0,如果不是二号门的时候
那么00010&上1<<x都是0,所以此时其它门都进不去,如果再拿到了三号钥匙加上之后变成了00110,代表二号三号钥匙都拿到了,然后到了三号门的
时候00110&(1<<3)00100或者到了二号门的时候00110&(1<<2)00010都是非0的,到其他门都是为0的-----
这样就很好的解决了钥匙的记录问题,这里有10把钥匙,所以数组要大于2的10次方
code
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int dx[]={,-,,};
int dy[]={,,-,};
char dzm[]={'A','B','C','D','E','F','G','H','I','J'};
char xzm[]={'a','b','c','d','e','f','g','h','i','j'};
struct point {
int x,y;
int step,dir;
};
int n,m,sx,sy;
int visit[][][];//记录钥匙
char map[][];
int bfs()
{
int i,j;
memset(visit,,sizeof(visit));
queue<point>Q;
point now,next;
now.x=sx;now.y=sy;
now.step=now.dir=;
visit[now.x][now.y][now.dir]=;
Q.push(now);
while (!Q.empty())
{
now=Q.front();
Q.pop();
if (map[now.x][now.y]=='^')
return now.step;
for (i=;i<;i++)
{
next.x=now.x+dx[i];
next.y=now.y+dy[i];
next.step=now.step+;
next.dir=now.dir;
if (map[next.x][next.y]=='*')continue;
if (next.x<||next.x>n||next.y<||next.y>m)continue;
if (map[next.x][next.y]<='J'&&map[next.x][next.y]>='A')
{
for (j=;j<;j++)
{
if (map[next.x][next.y]==dzm[j])
{
if ((next.dir&(<<j))!=)
{
if (visit[next.x][next.y][next.dir]==)
{
visit[next.x][next.y][next.dir]=;
Q.push(next);
}
}
}
}
}
else if (map[next.x][next.y]<='j'&&map[next.x][next.y]>='a')
{
for (j=;j<;j++)
{
if (map[next.x][next.y]==xzm[j])
{
if ((next.dir&(<<j))==)
next.dir+=(<<j);
if (visit[next.x][next.y][next.dir]==)
{
visit[next.x][next.y][next.dir]=;
Q.push(next);
}
}
}
}
else
{
if (visit[next.x][next.y][next.dir]==)
{
visit[next.x][next.y][next.dir]=;
Q.push(next);
}
}
}
}
return -;
}
int main()
{
int i,j,t;
while (~scanf("%d %d %d",&n,&m,&t))
{
getchar();
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
scanf(" %c",&map[i][j]);
if (map[i][j]=='@')
sx=i,sy=j;
}
}
int q=bfs();
if (q>=t)
printf("-1\n");
else
printf("%d\n",q);
}
return ;
}