考虑到就算是在同一个方格中,所持有的钥匙的不同也会影响到可达的点,无法直接跑最短路,同时注意到数据范围极小,
我们可以考虑把原图分层,即对于每个点,考虑在这个点所持有钥匙的搭配不同的情况下可达的点,
对于每种情况都构造出一个图,最后再把所有图合在一起,再连需要连的边即可。
- 所持有钥匙的搭配可以用二进制状态压缩处理
- 代码实现时,对于每个点,考虑在每种状态下,四周哪些点可达哪些点不可达,把需要连的边权为 $1$ 的边加入到总图中(走一个格花 $1$ 的时间);再考虑从当前状态可以转移到自己这个点的其他哪些状态,如在一个有钥匙的点上,没有这个钥匙的状态就都可以转移到有这个钥匙的对应的状态上,连一条边权为 $0$ 的边即可(捡钥匙不花时间)
- 时间复杂度1 $\mathcal{O}(NMP2^P+M_{\text{all}})$ $\Rightarrow$ $\mathcal{O}(NMP2^P)$ $\approx$ $1.02\times 10^6$
- 代码还有很多地方可以优化、简化,但为了和思路匹配并更加易懂并未进行优化,读者可自行思考
其实是我不会
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 10 + 10, M = 10 + 10, P = 10;
const int INF = 0x3f3f3f3f;
const int MAPN = N * M * (1 << P) + 10,
MAPM = MAPN * 4 + P * (1 << P - 1) +
10; //共 2^P 层,每层 NM 个点;每个点最多四个方向每个方向一条边,有钥匙的话上下状态之间还会有 2^(P-1)
//条权值为0的边
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //方向盘,x 从上到下行数,y 从左到右列数
int n, m, p;
int wall[N][M][4]; // wall[i][j][k]=INF 表示 i 行 j 列方格 k 方向为墙壁
int key[N][M]; //二进制状态压缩,key[i][j] 的二进制表示中从右到左第 k 位表示 i 行 j 列方格是否有第 k 种钥匙
int h[MAPN], e[MAPM], ne[MAPM], w[MAPM], idx; //邻接表存 bfs 用的分层后的总图
int dis[MAPN];
bool st[MAPN];
inline void speedup()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
inline int get_idx(const int x, const int y,
const int stat) //把原图中某种状态的某个方格映射到分层后的总图中,返回唯一对应的点的编号
{
return y + m * (x - 1) + n * m * stat;
}
inline void add(const int a, const int b, const int c) //有向有权边
{
w[++idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
inline void init_wall() //初始化边界
{
for (int i = 1; i <= n; i++)
wall[i][1][3] = wall[i][m][1] = INF;
for (int j = 1; j <= m; j++)
wall[1][j][0] = wall[n][j][2] = INF;
}
inline void make_graph()
{
init_wall();
memset(h, -1, sizeof(h));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int stat = 0; stat < 1 << p; stat++) //遍历每一个点的每一种状态,设置其可以走到的点(状态)
{
for (
int drct = 0; drct < 4;
drct++) //同层之间,四个方向看是否可以直接走、有门有对应的钥匙还是不能走,同时对应地在总图中进行连边
{
if (wall[i][j][drct] == INF)
continue;
if (!wall[i][j][drct] || stat >> wall[i][j][drct] - 1 & 1)
add(get_idx(i, j, stat), get_idx(i + dx[drct], j + dy[drct], stat), 1);
}
for (int k = 0; k < p;
k++) //同点不同层之间,看状态之间是否可以相互转移,同时对应地在总图中进行连边,注意权值为
// 0,拿钥匙不需要时间
if (stat >> k & 1 ^ 1 && key[i][j] >> k & 1)
add(get_idx(i, j, stat), get_idx(i, j, stat | 1 << k), 0);
}
}
}
}
inline int bfs() // 01 权值采用双端 bfs
{
memset(dis, 0x3f, sizeof(dis));
deque<int> q;
q.emplace_front(1);
dis[1] = 0;
while (!q.empty())
{
int tmp = q.front();
q.pop_front();
st[tmp] = 1;
for (int i = h[tmp]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = 1;
dis[j] = dis[tmp] + w[i];
if (j % (n * m) == 0) //第一次遍历到一定是最短路(bfs 特性),直接返回,不用管状态,是目标点就行
return dis[j];
if (!w[i])
q.emplace_front(j);
else
q.emplace_back(j);
}
}
}
return -1; //没路,输出 -1
}
int main()
{
speedup();
int k, s;
cin >> n >> m >> p;
cin >> k;
while (k--)
{
int x1, y1, x2, y2, g;
cin >> x1 >> y1 >> x2 >> y2 >> g;
//四种情况分类讨论进行墙/门的标记,注意方向,核心代码
if (x1 - x2 == 1)
wall[x1][y1][0] = wall[x2][y2][2] = g ? g : INF;
else if (x2 - x1 == 1)
wall[x1][y1][2] = wall[x2][y2][0] = g ? g : INF;
else if (y1 - y2 == 1)
wall[x1][y1][3] = wall[x2][y2][1] = g ? g : INF;
else if (y2 - y1 == 1)
wall[x1][y1][1] = wall[x2][y2][3] = g ? g : INF;
}
cin >> s;
while (s--)
{
int x, y, q;
cin >> x >> y >> q;
key[x][y] |= 1 << q - 1; //有钥匙,对应位设置,核心代码
}
make_graph(); //构造分层后总图,用于 bfs,核心代码
cout << bfs() << endl;
return 0;
}