这是第一次做关于位压缩的题，百度了一下才明白。搜索时用三维数组标记，只有添加了新钥匙才能走回路。因为只有10把钥匙，那么可以把10钥匙压缩二进制，比如1000就表示身上只要第4把钥匙的状态，110表示带有第2把和第3把钥匙，那么要判断当前的钥匙串有没有能打开当前门钥匙，那么就只要一个&运算就可以，因为11101110&00100000==00100000 这样就说明那一把钥匙在里面，若为0就不在这里面。如果对于当前点是一把钥匙的时候，只要|运算就可以了，11101110
| 00010000 z这样就把当前这把钥匙放进了钥匙串里面了
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std ;
int vis[25][25][1025] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1} ;
int n,m,k ;
char s[25][25] ;
struct zhang
{
int x,y,bu,key ;
} ;
int bfs(int x,int y)
{
queue<zhang>q ;
zhang current,next ;
memset(vis,0,sizeof(vis)) ;
current.x=x ;
current.y=y ;
current.bu=0 ;
current.key=0 ;
vis[current.x][current.y][0]=1 ;
q.push(current) ;
while(!q.empty())
{
current=q.front() ;
q.pop() ;
if(s[current.x][current.y]=='^'&¤t.bu<k)
return current.bu ;
for(int i=0;i<4;i++)
{
next.x=current.x+dx[i] ;
next.y=current.y+dy[i] ;
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&s[next.x][next.y]!='*'&¤t.bu<k)
{
next.bu=current.bu+1 ;
next.key=current.key ;
if(s[next.x][next.y]>='a'&&s[next.x][next.y]<='j')
{
int key=(1<<(s[next.x][next.y]-'a')) ;
next.key|=key ;
if(!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=1 ;
q.push(next) ;
}
}
else if(s[next.x][next.y]>='A'&&s[next.x][next.y]<='J')
{
int key=s[next.x][next.y]-'A' ;
if((next.key>>key)&1&&!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=1 ;
q.push(next) ;
}
}
else if(!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=1 ;
q.push(next) ;
}
}
}
}
return -1 ;
}
int main()
{
int ex,ey ;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
getchar() ;
for(int i=0;i<n;i++)
{
scanf("%s",s[i]) ;
for(int j=0;j<m;j++)
if(s[i][j]=='@')
{
ex=i ;
ey=j ;
}
}
printf("%d\n",bfs(ex,ey)) ;
}
return 0 ;
}