题目描述
1944 年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形,其南北方向被划分为 N 行,东西方向被划分为 M 列, 于是整个迷宫被划分为 N×M 个单元。
每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 2 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。
注意: 门可以从两个方向穿过,即可以看成一条无向边。
迷宫中有一些单元存放着钥匙,同一个单元可能存放 多把钥匙,并且所有的门被分成 P 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角,即 (N,M) 单元里,并已经昏迷。
迷宫只有一个入口,在西北角。
也就是说,麦克可以直接进入 (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
(双端队列bfs) $O(n^2 * 2^10)$
C++ 代码
//
// Created by Henry Yi on 2021-01-05.
//
#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 12, K = 155;
int key[N][N];
int g[N][N][N][1 << N];
int n, m, p, k, s;
int dist[N][N][1 << N];
bool st[N][N][1 << N];
int nX[] = {1, 0, -1, 0}, nY[] = {0, 1, 0, -1};
void bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1][1][0] = 0;
deque<pair<PII, PII>> queue;
queue.push_back({{0, 1}, {1, 0}});
while (queue.size()) {
auto t = queue.front();
queue.pop_front();
int distance = t.x.x, x = t.x.y, y = t.y.x, state = t.y.y;
st[x][y][state] = true;
for (int i = 0; i < 4; ++i) {
int tx = x + nX[i], ty = y + nY[i];
if (tx < 1 || tx > n || ty < 1 || ty > m || st[tx][ty][state]) continue;
if (g[x][y][tx][ty] == -1 || g[x][y][tx][ty] & state) {
if (dist[tx][ty][state] > distance + 1) {
dist[tx][ty][state] = distance + 1;
queue.push_back({{distance + 1, tx}, {ty, state}});
}
}
}
if (!st[x][y][state | key[x][y]] && dist[x][y][state | key[x][y]] > distance) {
dist[x][y][state | key[x][y]] = distance;
queue.push_front({{distance, x}, {y, state | key[x][y]}});
}
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &p, &k);
memset(g, -1, sizeof g);
for (int i = 0; i < k; ++i) {
int x1, y1, x2, y2, w;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w);
g[x1][y1][x2][y2] = 1 << w;
g[x2][y2][x1][y1] = 1 << w;
}
scanf("%d", &s);
for (int i = 1; i <= s; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
key[a][b] += 1 << c;
}
bfs();
int res = 0x3f3f3f3f;
for (int i = 0; i < 1 << N; ++i) {
res = min(res, dist[n][m][i]);
}
if (res == 0x3f3f3f3f) res = -1;
printf("%d\n", res);
}