题目描述
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形，其南北方向被划分为 N
行，东西方向被划分为 M 列， 于是整个迷宫被划分为 N×M个单元。
每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 2个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
注意： 门可以从两个方向穿过，即可以看成一条无向边。
迷宫中有一些单元存放着钥匙，同一个单元可能存放多把钥匙，并且所有的门被分成P类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即 (N,M)单元里，并已经昏迷。
迷宫只有一个入口，在西北角。
也就是说，麦克可以直接进入 (1,1)单元。
另外，麦克从一个单元移动到另一个相邻单元的时间为 1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。
输入格式
第一行有三个整数,分别表示 N,M,P的值。
第二行是一个整数 k，表示迷宫中门和墙的总数。
接下来 k行，每行包含五个整数，Xi1,Yi1,Xi2,Yi2,Gi：当 Gi≥1 时，表示 (Xi1,Yi1) 单元与 (Xi2,Yi2) 单元之间有一扇第 Gi 类的门，当 Gi=0 时，表示 (Xi1,Yi1) 单元与 (Xi2,Yi2)单元之间有一面不可逾越的墙。
接下来一行，包含一个整数 S，表示迷宫中存放的钥匙的总数。
接下来 S行，每行包含三个整数 Xi1,Yi1,Qi，表示 (Xi1,Yi1) 单元里存在一个能开启第 Qi类门的钥匙。
输出格式
输出麦克营救到大兵瑞恩的最短时间。
如果问题无解，则输出 -1。
数据范围
|Xi1−Xi2|+|Yi1−Yi2|=1,
0≤Gi≤P,
1≤Qi≤P,
1≤N,M,P≤10,
1≤k≤150
样例
输入样例：
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
输出样例：
14
历经波折的BFS
题意：一个长方形被划分为N*M个单元，每个单元之间：1.直接通过 2.上锁的门 3.无法通过
在有些单元里会有一些钥匙，拿起钥匙不需要时间，但是每移动一格都需要1个单位时间，对于上锁的门只要有对应的钥匙就可以打开通过，现在在左上角的第一个格子，要走到右下角的格子，求最短的时间
若是没有上锁的门这个条件，那么就是一个BFS问题，但是有了上锁的门后，可能需要先走到某个格子拿到钥匙再继续移动，且若是某个单元中有钥匙，那么一定是全部拿起。在最短路的问题中，我们的状态都是x,y坐标，从某个坐标转移到另一个坐标，但是这样定义已经不够了，我们还需要记录我们在某个点有多少钥匙（画图不易，放上听课的截图）
由数据范围，钥匙最多只有10种，所以可以想到用十位二进制压缩来存储，从最低位开始是第一种，最高位是第10种，哪一位为1就表示我们已经拿到了这把钥匙。那么在移动的时候，只有在三种状态下才可以更新状态，1.可以直接通过（花费时间1） 2.需要对应的钥匙才能通过（花费时间1） 3.当前单元有钥匙（花费时间0）。转移方式如上图
但是这个题在各个状态之间并不是一个拓扑图的关系，所以我们依然要用最短路的方式来求。这个图的所有边权只有0和1，那么可以使用双端队列来求解（边权为0插入队头，为1插入对尾，队列中依旧保持单调性和两段性，并且只有在点出队的时候才是最小值）。所以一旦出队的点已经到达了终点，那么就是所要求的最小值。
但是，这个题目并没有把图建好交给我们，而只是给出了墙和上锁的门，所以其他的边还需要我们自己创建，把已经标记过的边记录下来，不要创建重了。为了减少数组维数，可以把x,y压缩成一维，左上角编号为1，右下角为N*M。
（PS：最短路的算法基本都有st判重数组，但是用法不尽相同，要理解，曾经我也是一团浆糊……
BFS：由于出队和入队的时候就是最小值，所以只需要看是否已经走过，已经走过就不用再更新了；
双端队列和Dijstra：只有在出队的时候才是最小值，所以在出队的时候进行标记;
spfa：入队出队都不一定是最小值，标记某个点是不是在队列中，不要在队列中添加重复元素）
C++ 代码
#include<iostream>
#include<set>
#include<deque>
#include<cstring>
#define x first
#define y second
using namespace std;
//边数：每行最大N-1条，N行，列同理，双向边，2*2*N*(N-1)，开到400+
const int N=15,M=410,P=1<<10;
typedef pair<int,int> PII;
int n,m,p,k,s;//n行，m列，p种钥匙
int g[N][N];//记录每个点的格子编号
int h[N*N],e[M],ne[M],w[M],idx;
set<PII> edge;
int dist[N*N][P],st[N*N][P];
int key[N*N];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void build(){
//枚举每个点，然后枚举每个点的上下左右四个方向
//不可以只枚举i,j，只有相邻的两个单元才建立边
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<4;k++){
int a=i+dir[k][0],b=j+dir[k][1];
if(!a||a>n||!b||b>m) continue;
if(edge.count({g[i][j],g[a][b]})) continue;
// edge.insert({g[i][j],g[a][b]});
add(g[i][j],g[a][b],0);
}
}
}
}
int bfs(){
memset(dist,0x3f,sizeof dist);
dist[1][0]=0;
deque<PII>q;
q.push_back({1,0});//单元，钥匙状态
while(q.size()){
PII t=q.front();
q.pop_front();
if(st[t.x][t.y]) continue;
st[t.x][t.y]=1;
if(t.x==n*m) return dist[t.x][t.y];
if(key[t.x]){
int state=t.y|key[t.x];//捡起钥匙，状态更新
if(dist[t.x][t.y]<dist[t.x][state]){
dist[t.x][state]=dist[t.x][t.y];
q.push_front({t.x,state});//插入对头
}
}
for(int i=h[t.x];~i;i=ne[i]){
int j=e[i];
//如果当前是门，且拥有的钥匙状态的第w[i]-1位是0，说明打不开这扇门
if(w[i] && !((t.y>>(w[i]-1))&1)) continue;
if(dist[j][t.y]>dist[t.x][t.y]+1){
dist[j][t.y]=dist[t.x][t.y]+1;
q.push_back({j,t.y});//插入队尾
}
}
}
return -1;//如果在队列中没有返回，那么不可达
}
int main(){
cin>>n>>m>>p>>k;
memset(h,-1,sizeof h);
for(int i=1,cnt=1;i<=n;i++){
for(int j=1;j<=m;j++)
g[i][j]=cnt++;//初始化每个单元的编号
}
for(int i=0;i<k;i++){
int x1,y1,x2,y2,t;
cin>>x1>>y1>>x2>>y2>>t;
int a=g[x1][y1],b=g[x2][y2];
edge.insert({a,b});//已经建立的边记录
edge.insert({b,a});
//把门的类型当作边权，如果是墙，就不建立
if(t) add(a,b,t),add(b,a,t);//谁能想到我改了半个小时的代码就是因为这里把逗号敲成了分号呢……
}
build();
cin>>s;
for(int i=0;i<s;i++){
int a,b,t;
cin>>a>>b>>t;
key[g[a][b]]|=1<<(t-1);//节省空间，将钥匙类型-1，并进行或运算，一个单元可能有多把钥匙
}
cout<<bfs();
return 0;
}
