题面

题目链接

大秦 为你打开 题目传送门

备用题面

看不了题目的看下面喵！

有一个矩形状的迷宫，它被分为 $n \times m$ 个位置。有序对（行号，列号）表示迷宫中的位置，行号从 $1$ 到 $n$ 编号，列号从 $1$ 到 $m$ 编号。

从当前位置移动到下一个位置花费一步，而且只有同时满足以下条件才能移动到下一个位置：

1、下一个位置与当前位置相邻（上下或左右，4个方向）；

2、开着的门是可以通行的，但锁着的门不是；

3、不能通过一堵墙。

游戏开始时，所有的门是锁着的，一种类型的钥匙只能打开对应类型的门。只有在拿到对应钥匙之后才能打开相应的门。

经过某格子时，即可获得该格子所有钥匙。

请计算一下从 $(1,1)$ 到 $(n,m)$ 最少要花费几步。

思路

典型的走迷宫 BFS 题。但是这次他有门和钥匙，那我们状压的东西也很明显了，就是我们身上有几把钥匙，这样就可以解决门的问题了，其他基本就是最最简单的 BFS 。详见代码。

代码

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
#include<bits/stdc++.h>
using namespace std;

struct node {
    int x, y, k, tot;
};

int n, m, p;
int keys[60][60];
int wall[60][60][60][60];

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int vis[60][60][1 << 12];

void Input() {
    memset(wall, -1, sizeof(wall));
    scanf("%d%d%d", &n, &m, &p);
    int k, s;
    int x, y, x2, y2, g;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d%d%d%d%d", &x, &y, &x2, &y2, &g);
        wall[x][y][x2][y2] = wall[x2][y2][x][y] = g; // 门只以最后一个门为主
    }
    scanf("%d", &s);
    for (int i = 1; i <= s; i++) {
        scanf("%d%d%d", &x, &y, &g);
        keys[x][y] |= (1 << (g - 1)); // 因为一个格子可以有多个钥匙
    }
}

void Work() {
    queue<node >q;
    q.push((node) { 1, 1, keys[1][1], 0 });
    vis[1][1][keys[1][1]] = 1;
    while (!q.empty()) {
        node f = q.front(); q.pop();
        if (f.x == n && f.y == m) {
            printf("%d", f.tot);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int x = f.x + dx[i];
            int y = f.y + dy[i];

            if (x<1 || x>n || y<1 || y>m) continue;
            if (wall[f.x][f.y][x][y] == 0) continue;
            if (vis[x][y][f.k | keys[x][y]]) continue;

            int dr = wall[f.x][f.y][x][y];
            int ke = f.k | keys[x][y];
            if (vis[x][y][ke] == 0 && (dr == -1 || (dr > 0 && (f.k & (1 << (dr - 1)))))) {
                vis[x][y][ke] = 1;
                q.push((node) { x, y, ke, f.tot + 1 });
            }
        }
    }
    printf("-1");
}

int main() {
    Input();
    Work();
    return 0;
}