1131. 拯救大兵瑞恩 - AcWing题库
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形，其南北方向被划分为 N 行，东西方向被划分为 M 列， 于是整个迷宫被划分为 N×M 个单元。
每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 22 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
注意： 门可以从两个方向穿过，即可以看成一条无向边。
迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 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处理。如果加上门之后我们还用d[i]表示i点的最短距离的话是无法表示所有状态的（无法判断当前是否有钥匙），因此直观的想法是增加一些状态。
其实最短路的拆点过程类似与dp的状态压缩。在所有最短路中需要拆点或分层的问题中，都可以使用dp的分析方式。
因此我们可以进行状态划分：不重不漏，将状态转移所依据的状态体现出来；
d[x,y,state]表示：所有从起点走到（x,y)这个格子，且当前已经拥有的钥匙是state（类似状态压缩中的二进制表示）的所有路线的集合。值表示此状态下到达该点的最小值。
状态转移：
1.（x,y)这里有一些钥匙，那么可以直接将所有钥匙拿起，state | key :
d[x,y,state | key]=min(d[x,y,state | key],d[x,y,state]);
2.向上下左右四个方向走。（1）没有门和墙；（2）有门，且有匹配的钥匙（a,b):
d[a,b,state]=min(d[a,b,state],d[a,b,state]+1)
这里虽然使用dp的方式分析，但这道题是无法直接使用dp的方式处理的，因为：dp方式处理需要确保状态之间有拓扑序，本题中的状态转移过程可能存在环形，也就是后效性。
dp相当于求拓扑图上的最短路。因此我们可以直接使用最短路问题处理dp问题。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N = 100 + 5, M = (N + 1) * N * 2,P=1<<10;
int n, m, p, k;
int h[N], e[M], w[M], ne[M], idx;
int g[N][N], d[N*N][P],key[P];
int vis[N][P];
set<PII>st;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build() {
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int u = 0; u < 4; u++) {
int a = i + dx[u], b = j + dy[u];
if (a > n || a <= 0 || b>m || b<=0)continue;
if (!st.count({ g[i][j],g[a][b] }))
add(g[i][j], g[a][b], 0);
}
}
}
}
int bfs() {
memset(d, 0x3f, sizeof d);
d[1][0] = 0;
deque<PII>q;
q.push_back({ 1,0 });
while (!q.empty()) {
PII t = q.front();
q.pop_front();
if (vis[t.first][t.second])continue;
vis[t.first][t.second] = 1;
if (t.first == n * m)return d[t.first][t.second];
if (key[t.first]) {
int state = t.second|key[t.first];
if (d[t.first][state] > d[t.first][t.second]) {
d[t.first][state] = d[t.first][t.second];
q.push_back({ t.first,state });
}
}
for (int i = h[t.first]; i != -1; i = ne[i]) {
int j = e[i];
if (w[i] && !(t.second >> w[i] - 1 & 1))continue;
if (d[j][t.second] > d[t.first][t.second] + 1) {
d[j][t.second] = d[t.first][t.second] + 1;
q.push_back({ j,t.second });
}
}
}
return -1;
}
int main() {
cin >> n >> m >> p >> k;
for (int i = 1,t=1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[i][j] = t++;
}
}
memset(h, -1, sizeof h);
for (int i = 1,a,b,a1,b1,c; i <= k; i++) {
scanf("%d%d%d%d%d", &a, &b, &a1, &b1, &c);
st.insert({ g[a1][b1],g[a][b] });
st.insert({ g[a][b],g[a1][b1] });
if (c)add(g[a][b], g[a1][b1], c), add(g[a1][b1], g[a][b], c);
}
build();
int s;
cin >> s;
while (s--) {
int x, y, c;
cin >> x >> y >> c;
key[g[x][y]] |= 1 << c - 1;
}
cout << bfs() << endl;
return 0;
}
