算法：广搜+位运算；
题目描述
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训，把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
每组测试数据之间有一个空行。
输出
针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。
样例输入
4 5 17
@A.B.
a*.*.
*..*^
c..b*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
样例输出
16
-1
代码：
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <stdio.h>
using namespace std;
char ch[21][21];
int n,m,t,p,q,s,st;
int a[4][2]={1,0,-1,0,0,1,0,-1};
int b[21][21][1030];
struct dot
{
int x,y,step;
int nkey;
};
int cmp(int ax,int ay)
{
if(ax>=0&&ax<n&&ay>=0&&ay<m) return 1;
return 0;
}
int bfs()
{
queue<dot>que;
dot cur,loer;
cur.x=p;cur.y=q;cur.step=0;
cur.nkey=0;
que.push(cur);
memset(b,0,sizeof(b));
b[p][q][cur.nkey]=1;
while(que.size())
{
loer=que.front();
que.pop();
if(loer.x==s&&loer.y==st)
return loer.step;
for(int i=0;i<4;i++)
{
cur=loer;
cur.x+=a[i][0];
cur.y+=a[i][1];
if(cmp(cur.x,cur.y)&&ch[cur.x][cur.y]!='*'&&!b[cur.x][cur.y][cur.nkey])
{
if(ch[cur.x][cur.y]=='.')
{ cur.step++;que.push(cur);b[cur.x][cur.y][cur.nkey]=1; }
if(ch[cur.x][cur.y]>='a'&&ch[cur.x][cur.y]<='j')
{
//int key=1<<(ch[cur.x][cur.y]-'a');
int key=pow(2,ch[cur.x][cur.y]-'a');
if(!b[cur.x][cur.y][cur.nkey|key])
{
cur.nkey=cur.nkey|key;
cur.step++;
b[cur.x][cur.y][cur.nkey]=1;
que.push(cur);
}
}
if(ch[cur.x][cur.y]>='A'&&ch[cur.x][cur.y]<='J')
{
//int key=1<<(ch[cur.x][cur.y]-'A');
int key=pow(2,ch[cur.x][cur.y]-'A');
if(cur.nkey&key)
{ cur.step++;b[cur.x][cur.y][cur.nkey]=1;que.push(cur);}
}
}
}
}
return -1;
}
int main()
{
int i,j,k;
while(cin>>n>>m>>t)
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='@')
{
p=i;q=j;
ch[i][j]='.';
}
if(ch[i][j]=='^')
{
s=i;st=j;
ch[i][j]='.';
}
}
}
int ans=bfs();
if(ans>=0&&ans<t) cout<<ans<<endl;
else cout<<"-1"<<endl;
}
return 0;
}