题意：这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始 Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一 个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮 他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
记得去年网赛有这样一题，当时不会状压，搞不出来，现在看起来还是很水的
得到钥匙的状态用二进制表示，比如有A钥匙即为1，有A，C钥匙即为101
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int vis[][][];
char s[][];
int d[][]={,,,,-,,,-};
int n,m,tt,time;
struct node
{
int x,y,t,key;
node(){}
node(int xx,int yy,int tt,int kk)
{
x=xx,y=yy,t=tt,key=kk;
}
}st,ed;
void bfs()
{
node now,next;
queue<node> q;
q.push(node(st.x,st.y,,));
vis[st.x][st.y][]=;
while(!q.empty())
{
now=q.front();
q.pop();
if(now.x==ed.x&&now.y==ed.y)
{
if(now.t<time)
{
printf("%d\n",now.t);
return;
}
else
break;
}
for(int i=;i<;i++)
{
next.x=now.x+d[i][];
next.y=now.y+d[i][];
next.t=now.t+;
next.key=now.key;
if(next.x>=&&next.y>=&&next.x<n&&next.y<m&&s[next.x][next.y]!='*')
{
if('A'<=s[next.x][next.y]&&s[next.x][next.y]<='J')
{
int key=<<(s[next.x][next.y]-'A');
if((next.key&key)&&!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=;
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'));
next.key=(next.key|key);
if(!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=;
q.push(next);
}
}
else
{
if(!vis[next.x][next.y][next.key])
{
vis[next.x][next.y][next.key]=;
q.push(next);
}
}
}
}
}
printf("-1\n"); }
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d%d%d",&n,&m,&time)!=EOF)
{
for(i=;i<n;i++)
{
scanf("%s",s[i]);
for(j=;j<m;j++)
{
if(s[i][j]=='@') st.x=i,st.y=j;
if(s[i][j]=='^') ed.x=i,ed.y=j;
}
}
memset(vis,,sizeof(vis));
bfs();
}
}