传送门 ↬\looparrowright

题目描述

19441944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 nn 行，东西方向被划分为 mm 列，于是整个迷宫被划分为 n×mn\times m 个单元。每一个单元的位置可用一个有序数对（单元的行号，单元的列号）来表示。南北或东西方向相邻的 22 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 pp 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即 (x,y)(x,y) 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 (1,1)(1,1) 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 11，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入格式

第 11 行有 33 个整数，分别表示 n,m,pn,m,p 的值。
第 22 行是 11 个整数 kk，表示迷宫中门和墙的总数。
第 i+2i+2 行 (1⩽i⩽k)(1\leqslant i\leqslant k)，有 55 个整数，依次为 xi1,yi1,xi2,yi2,gix_{i1},y_{i1},x_{i2},y_{i2},g_i。当 gi⩾1g_i \geqslant 1 时，表示 (xi1,yi1)(x_{i1},y_{i1}) 单元与 (xi2,yi2)(x_{i2},y_{i2}) 单元之间有一扇第 gig_i 类的门；当 gi=0g_i=0 时，表示 (xi1,yi1)(x_{i1},y_{i1}) 单元与 (xi2,yi2)(x_{i2},y_{i2}) 单元之间有一堵不可逾越的墙。其中，∣xi1−xi2∣+∣yi1−yi2∣=1|x_{i1}-x_{i2}|+|y_{i1}-y_{i2}|=1，0⩽gi⩽p0\leqslant g_i\leqslant p。
第 k+3k+3 行是一个整数 ss，表示迷宫中存放的钥匙总数。
第 k+3+jk+3+j 行 (1⩽j⩽s)(1\leqslant j\leqslant s)，有 33 个整数，依次为 xi1,yi1,qix_{i1},y_{i1},q_i 表示第 jj 把钥匙存放在 (xi1,yi1)(x_{i1},y_{i1})单元里，并且第 jj 把钥匙是用来开启第 qiq_i 类门的。（其中 1⩽qi⩽p1\leqslant q_i\leqslant p）。
输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出 −1-1。

输入输出样例

输入 #1

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

输出 #1

14

说明/提示

∣xi1−xi2∣+∣yi1−yi2∣=1|x_{i1}-x_{i2}|+|y_{i1}-y_{i2}|=1，0⩽gi⩽p0\leqslant g_i\leqslant p。
n,m,p⩽10n,m,p\leqslant10，k<150k<150，s⩽14s\leqslant 14。

分析

每走一次花费的时间都为 11，对于每次操作花费相同的问题，可以考虑用 BFS\text{BFS} 解决。
用 map<pair<CPoint,CPoint>,int> 记录两个位置之间的墙或门，若为墙则记为 −1-1，表示不可逾越。用 map<CPoint,vector<int>> 记录某个位置的所有钥匙。便于查询某个位置的信息。
由于每个钥匙都可重复利用，所以同一种类的所有门只要一把钥匙就可以全部打开。不妨采用状态压缩的方式，定义整数 hashas，其第 k−1k-1 位（二进制位，由低位到高位编号，最低位为第 00 位）若为 11，表示手上已经有打开第 kk 类门的钥匙，其中 k⩾1k\geqslant 1。
定义状态 (x,y,has,step)(x,y,has,step)，表示当前位于位置 (x,y)(x,y)，钥匙的拥有情况为 hashas，且已经走了 stepstep 步。可以用 BFS\text{BFS} 遍历所有状态，定义函数 vis(i,j,k)vis(i,j,k) 记录状态是否已经遍历过；若 vis(i,j,k)vis(i,j,k) 为 11，表示位于位置 (i,j)(i,j)，且钥匙拥有情况为 kk 的状态已经遍历过，不必再返回此状态。
搜索时，从 (x,y)(x,y)走到 (x+Δx,y+Δy)(x+\Delta x,y+\Delta y)，需要考虑：① (x+Δx,y+Δy)(x+\Delta x,y+\Delta y) 是否越界；② (x,y)(x,y) 和 (x+Δx,y+Δy)(x+\Delta x,y+\Delta y) 之间是否有障碍；③ 走到(x+Δx,y+Δy)(x+\Delta x,y+\Delta y) 后的状态是否已经遍历到；④ 获得位于 (x+Δx,y+Δy)(x+\Delta x,y+\Delta y) 的钥匙。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4011
Date: 8/2/2020
Description: BFS
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<utility>
using namespace std;
const int N=12;
const int inf=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
struct CPoint
{
	int r;//行
	int c;//列
	bool operator<(const CPoint& A)const
	{
		if(r==A.r) return c<A.c;
		else return r<A.r;
	}
};
struct state
{
	int x;
	int y;
	int has;
	int step;
};
map<pair<CPoint,CPoint>,int>gap;
map<CPoint,vector<int>>key;//某位置的所有钥匙
int n,m;
int p;//p类门
int k;//门和墙的总数
int s;//钥匙总数
bool vis[N][N][N<<12];
int bfs();
int main()
{
	cin>>n>>m>>p;
	cin>>k;//墙和门的总数
	int i;
	for(i=1;i<=k;i++) 
	{
		int x1,y1,x2,y2,g;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
		if(!g) g=-1;//不可逾越
		gap[make_pair(CPoint{x1,y1},CPoint{x2,y2})]=g;
		gap[make_pair(CPoint{x2,y2},CPoint{x1,y1})]=g;
	}
	cin>>s;//钥匙总数
	for(i=1;i<=s;i++)
	{
		int x,y,q;
		scanf("%d%d%d",&x,&y,&q);
		//(x,y) 有钥匙q
		key[CPoint{x,y}].push_back(q);
	}
	if(n==1&&m==1) cout<<0<<endl;
	else cout<<bfs()<<endl;
	return 0;
}
int bfs()
{
	int ans=inf;
	int _=0;
	for(auto i:key[CPoint{1,1}]) _|=(1<<i-1);
	vis[1][1][_]=1;
	queue<state>q;
	q.push(state{1,1,_,0});
	while(!q.empty())
	{
		state temp=q.front();
		q.pop();
		int x,y,has,step;
		for(register int i=0;i<4;i++)
		{
			x=temp.x+dx[i];
			y=temp.y+dy[i];
			if(x<1||x>n||y<1||y>m) continue;
			if(gap.count(make_pair(CPoint{temp.x,temp.y},CPoint{x,y})))
			{
				int barrier;
				barrier=gap[(make_pair(CPoint{temp.x,temp.y},CPoint{x,y}))];
				if(~barrier)
				{
					//没钥匙
					if(!(temp.has&(1<<barrier-1)))
					{
						continue;
					}
				}
				else continue;//不可逾越
			}
			step=temp.step+1;
			has=temp.has;
			for(auto j:key[CPoint{x,y}]) has|=(1<<j-1);
			if(vis[x][y][has]) continue;
			q.push(state{x,y,has,step});
			vis[x][y][has]=1;
			//到达终点
			if(x==n&&y==m) ans=min(ans,step);
		}
	}
	return ans==inf?-1:ans;
}