|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
const int N = 105, M = 12;
|
|
|
typedef pair<int, int> PII;
|
|
|
|
|
|
int g[N][N]; // 两个位置之间的间隔是什么，可能是某种门，或者是墙
|
|
|
int key[N]; // 某个坐标位置上有哪些钥匙，这是用数位压缩记录的,方便位运算
|
|
|
int dis[N][1 << M]; // 哪个位置，在携带不同的钥匙情况下的状态
|
|
|
int n, m; // n行m列
|
|
|
int k; // 迷宫中门和墙的总数
|
|
|
int p; // p类钥匙
|
|
|
int dx[] = {-1, 0, 1, 0}; // 上右下左
|
|
|
int dy[] = {0, 1, 0, -1}; // 上右下左
|
|
|
|
|
|
// 二维转一维的办法,坐标从(1,1)开始
|
|
|
int get(int x, int y) {
|
|
|
return (x - 1) * m + y;
|
|
|
}
|
|
|
|
|
|
int bfs() {
|
|
|
memset(dis, 0x3f, sizeof dis); // 初始化距离
|
|
|
queue<PII> q; // bfs用的队列
|
|
|
|
|
|
int S = get(1, 1); // 从编号1出发
|
|
|
q.push({S, key[S]}); // 位置+携带钥匙的压缩状态 = 现在的真正状态
|
|
|
dis[S][key[S]] = 0; // 初始状态的需要走的步数为0
|
|
|
|
|
|
while (q.size()) {
|
|
|
PII x = q.front();
|
|
|
q.pop();
|
|
|
|
|
|
int u = x.first; // 出发点编号
|
|
|
int st = x.second; // 钥匙状态,为状态压缩的数字
|
|
|
|
|
|
// dis[u][st]:到达了n*m,并且，当前状态是st: 找到大兵瑞恩就结束了,不用管最终的钥匙状态是什么
|
|
|
// 是什么都是符合拯救大兵的目标的
|
|
|
if (u == n * m) return dis[u][st];
|
|
|
|
|
|
// 四个方向
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
// 注意这里我是将格子编号从1开始，因此将其转化为坐标时需要先减一再加一
|
|
|
int tx = (u - 1) / m + 1 + dx[i]; // 下一个位置
|
|
|
int ty = (u - 1) % m + 1 + dy[i];
|
|
|
|
|
|
int T = get(tx, ty); // 要去的坐标位置T
|
|
|
|
|
|
/*
|
|
|
g[z][T] == 0 有墙，不能走
|
|
|
g[z][T] > 0 有门，有钥匙能走，无钥匙不能走
|
|
|
g[z][T] == -1 随便走
|
|
|
*/
|
|
|
// 出界或有墙,没有办法转移
|
|
|
if (tx == 0 || ty == 0 || tx > n || ty > m || g[u][T] == 0) continue;
|
|
|
|
|
|
// 有门,并且, st这个状态中没有带过来当前类型的钥匙
|
|
|
if (g[u][T] > 0 && !(st >> g[u][T] & 1)) continue;
|
|
|
|
|
|
// 捡起钥匙不会增加成本，所以，无条件捡起来钥匙
|
|
|
int ST = st | key[T];
|
|
|
|
|
|
// 如果这个状态没有走过
|
|
|
if (dis[T][ST] == INF) {
|
|
|
q.push({T, ST}); // 入队列
|
|
|
dis[T][ST] = dis[u][st] + 1; // 步数加1
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
// 一直没走到，返回-1
|
|
|
return -1;
|
|
|
}
|
|
|
int main() {
|
|
|
scanf("%d %d %d %d", &n, &m, &p, &k); // 地图n行m列，p类钥匙,k:迷宫中门和墙的总数
|
|
|
|
|
|
// 地图初始化
|
|
|
memset(g, -1, sizeof g);
|
|
|
|
|
|
// 1、将图记下来
|
|
|
int x1, y1, x2, y2, z1, z2, z;
|
|
|
while (k--) { // 读入迷宫中门和墙
|
|
|
// z=0:墙，z ={1,2,3,4...}哪种类型的门
|
|
|
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &z);
|
|
|
// 二维转化一维
|
|
|
// Q:为什么一定要二维转一维呢？不转直接用二维不行吗？
|
|
|
// A:点是一个二维信息，将坐标转换为点的编号，这样数组不用声明更多维度，代码更简单
|
|
|
z1 = get(x1, y1), z2 = get(x2, y2);
|
|
|
// 记录两个位置之间的间隔是:墙？某种类型的门？
|
|
|
g[z1][z2] = g[z2][z1] = z; // 无向图
|
|
|
}
|
|
|
|
|
|
int s;
|
|
|
scanf("%d", &s);
|
|
|
while (s--) { // 枚举每把钥匙
|
|
|
scanf("%d %d %d", &x1, &y1, &z); // 位置+钥匙类型
|
|
|
// 利用状态压缩，描述此位置上有钥匙
|
|
|
// get(x1,y1)--->1维转换后的数字
|
|
|
// key[get(x1,y1)]利用二进制+位运算，记录此位置有哪些类型的钥匙,因为一个位置可以有多个类型的钥匙，所以采用 |运算符进行累加
|
|
|
// 1 << z ：放过最后一位，将倒数第z位设置为数字1
|
|
|
key[get(x1, y1)] |= 1 << z;
|
|
|
}
|
|
|
// 宽搜
|
|
|
printf("%d\n", bfs());
|
|
|
return 0;
|
|
|
}
|
