题面：
题目中文大意：
这个故事发生在“星际迷航”的背景下。
“星际争霸”的副队长史波克落入克林贡的诡计中，被关押在他们的母亲星球Qo’noS上。
企业的上尉詹姆斯·T·柯克（James T. Kirk）不得不乘宇宙飞船去救他的副手。幸运的是，他偷走了史波克所在的迷宫地图。
迷宫是一个矩形，它有n行垂直和m列水平，换句话说，它被分为n * m个位置。有序对（行号，列号）表示迷宫中的位置。柯克从当前位置移动到下一个花费1秒。而且他只有在以下情况下才能移动到下一个位置：
下一个位置与当前柯克的位置相邻（上下或左右）（4个方向）
开着的门是可以通行的，但锁着的门不是。
柯克不能通过一堵墙
有几种门是默认锁定的。钥匙只能打开相同类型的门。柯克必须在打开相应的门之前拿到钥匙，这样很浪费时间。
柯克的初始位置是（1，1），而史波克位于（n，m）的位置。你的任务是帮助Kirk尽快找到史波克。
Input
输入包含很多测试样例。
每个测试样例由几行组成。第一行中有三个整数，分别代表n，m和p (1<= n, m <=50, 0<= p <=10).
第二行只列出一个整数k，表示门和墙的总数(0<= k <=500).
在下面的k行中有5个整数，表示 i1, y i1, x i2, y i2, g i; 当g i >=1,表示在位置 (x i1, y i1) 和 (x i2, y i2)之间存在类型gi的门；当g i = 0,说明 (x i1, y i1)和 (x i2, y i2),之间存在一堵墙 ( | x i1 - x i2 | + | y i1 - y i2 |=1, 0<= g i <=p )
下面的行是一个整数S，表示迷宫中的钥匙的总数。(0<= S <=50).
在下面的S行中有三个整数，分别表示x i1, y i1和q i这意味着类型为qi的钥匙位于位置 i (x i1, y i1), (1<= q i<=p).
Output
输出Kirk可能达到史波克的可能最小的秒数。
如果没有可能的计划，输出-1。
Sample Input
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
Sample Output
14
分析：
此题应使用广度优先搜索（BFS）
状态压缩：有10种钥匙，那么我们用10位二进制来存储钥匙串（即一个int整型变量），第i-1位是1表示有第i种钥匙，为0则没有钥匙
用位运算来判断是否能通过门（这些操作很常用，应牢记）
将第i种钥匙加入钥匙串key
代码:key|=(1<<(i-1))
例：key=0010 ，i=4，1<<(i-1)=1000，0010|1000=1010拿着钥匙串key,是否能通过第i种门
代码：if(key&(1<<(i-1)==0) continue
例：（没拿到第5种钥匙，想通过第5种门）key=01101，i=5，1<<(i-1)=10000，00101|10000=0，通不过，continue
（拿到第4种钥匙，想通过第4种门）key=01101，i=4，1<<(i-1)=01000，00101|10000=01000，可通过
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 56
#define maxqu 50*50*(1<<11)+10
using namespace std;
int n,m,p,k,s;
struct node{
int x;
int y;
int step;
int key;//存储钥匙
};
node now,nex;
node queue[maxqu];
int door[maxn][maxn][maxn][maxn];//邻接矩阵存门
int keys[maxn][maxn];//二维数组存储每一个点的钥匙
int used[maxn][maxn][2055];//标志是否走过
const int walkx[4]={1,-1,0,0},walky[4]={0,0,1,-1};
int fread(){//快速输入
int x=0;
char c=getchar();
int sign=1;
while(c<'0'||c>'9') {
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*sign;
}
bool judge(int x1,int y1,int x2,int y2){
if(door[now.x][now.y][nex.x][nex.y]==0) return false;//有墙
if(x2>=1&&x2<=n&&y2>=1&&y2<=m) return true;
else return false;
}
int bfs(){
int head=0,tail=0;
int tmp;
queue[0].x=1;
queue[0].y=1;
queue[0].step=0;
queue[0].key|=keys[1][1];//起点有钥匙的特判
memset(used,0,sizeof(used));
used[1][1][queue[0].key]=1;
do{
now=queue[head];
if(now.x==n&&now.y==m) return now.step;
for(int i=0;i<4;i++){
nex.x=now.x+walkx[i];
nex.y=now.y+walky[i];
nex.key=now.key;
nex.step=now.step;
if(judge(now.x,now.y,nex.x,nex.y)){
if(door[now.x][now.y][nex.x][nex.y]>0){//开门
tmp=door[now.x][now.y][nex.x][nex.y]-1;
if((nex.key&(1<<tmp))==0) continue;
}
if(keys[nex.x][nex.y]>0){//拿钥匙
nex.key|=keys[nex.x][nex.y];
}
if(used[nex.x][nex.y][nex.key]==1) continue;
used[nex.x][nex.y][nex.key]=1;
tail++;
queue[tail].x=nex.x;
queue[tail].y=nex.y;
queue[tail].key=nex.key;
queue[tail].step=nex.step+1;
}
}
head++;
}while(head<=tail);
return -1;
}
int main(){
// freopen("data.txt","r",stdin);
int x1,y1,x2,y2,v;
while(cin>>n>>m>>p){
memset(door,-1,sizeof(door));
memset(keys,0,sizeof(keys));
k=fread();
for(int i=1;i<=k;i++){
x1=fread();
y1=fread();
x2=fread();
y2=fread();
v=fread();
door[x1][y1][x2][y2]=v;//>0门，=0墙，-1无
door[x2][y2][x1][y1]=v;
}
cin>>s;
for(int i=1;i<=s;i++){
x1=fread();
y1=fread();
v=fread();
keys[x1][y1]|=(1<<(v-1));//预处理钥匙，注意一个位置有多个钥匙的情况
}
cout<<bfs()<<endl;
}
}