开始时候只用了BFS，显然超时啊，必然在结构体里加一个数组什么的判重啊，开始用的一个BOOL数组，显然还是不行，复杂度高，每次都要遍历数组来判重；后百度之，学习了二进制状态压缩，其实就用一个二进制数来表示当前状态，然后就可以用简单快速位运算来操作了。
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
char a[30][30];
int mark[30][30][1025]; //判重，坐标+钥匙数，二进制表示，每位代表不同钥匙，1有，0无。
int minn=99999;
int f[4][2]={0,1,0,-1,1,0,-1,0};
struct xy
{
int x,y;
int count; // 已经走的步数
int key; // 对应一个二进制数，如0001，在第一位有一把钥匙。
};
void bfs(xy from,int t,int n,int m)
{
queue<xy>q;
q.push(from);
while(!q.empty())
{
xy cur=q.front();
q.pop();
for(int i=0;i<4;i++)
{
xy next(cur);
next.x+=f[i][0];
next.y+=f[i][1];
if(next.x>=0&&next.y>=0&&next.x<n&&next.y<m&&a[next.x][next.y]!='*'&&mark[next.x][next.y][next.key]==0)
{
if(a[next.x][next.y]>='A'&&a[next.x][next.y]<='J')
{
if((next.key&(1<<(a[next.x][next.y]-'A')))==0)continue; //&的优先级比==低！！按位与来判断有无我这把钥匙
}
next.count++;
if(a[next.x][next.y]>='a'&&a[next.x][next.y]<='j')
{
next.key=next.key|(1<<(a[next.x][next.y]-'a')); //按位或来添加这把钥匙。
}
if(next.count==t){return;}
if(a[next.x][next.y]=='^'){minn=next.count;return;}
q.push(next);
mark[next.x][next.y][next.key]=1;
}
}
}
return;
}
int main()
{
int n,m,t;
while(cin>>n>>m>>t)
{
xy from;
minn=99999;
memset(mark,0,sizeof(mark));
from.count=0;
from.key=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='@'){from.x=i;from.y=j;}
}
bfs(from,t,n,m);
if(minn==99999)cout<<-1<<endl;
else cout<<minn<<endl;
cout<<endl;
}
}