1131. 拯救大兵瑞恩（dp思想运用，set）

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;
}

?