例 3 蓝桥杯 —— 迷宫与陷阱展开目录
这道题迷宫中多了一些花样。一是迷宫中有陷阱，由 X 表示。除非处于无敌状态，否则不能经过陷阱。二是有些位置到达后会自动获得无敌状态，持续 K 步。我们可以看一下样例给的两个数据：
这两个地图其实是一样的。区别在于左边的数据无敌状态持续 3 秒，可以拿到无敌之后经过右上角的陷阱到达终点。右边的数据无敌只持续 1 秒，所以拿到无敌来不及经过右上角的陷阱无敌就消失了，所以只能绕道左下角到达终点
由于陷阱和无敌的引入，这道题目变得很复杂。首先我是不是可以从一个位置 A 移动到位置 B 变得不确定了。如果 B 是陷阱，那么必须知道之前 K 步是不是获得过无敌，才能知道是不是可以移动到 B
其次，最优的路径可能走回头路。我们看上面第一个样例就是走回头路的例子，我们为了获得无敌两次经过 (0, 2) 这个点。此外题目本身还隐藏着一些陷阱。比如题目说第一次到达无敌位置会自动获得无敌状态；此后再到达该位置不会再获得无敌。如果我们考虑每个位置无敌还在不在的话，这个题目会变得更加复杂。但其实即便无敌一直存在，可以反复获得，我们的最优路线也不会经过一个无敌位置 2 次
如果我们仍把一个位置看成一个节点的话，我们会发现两个节点是不是有边相连这件事是不确定的。但是我们如果我们把一个状态看成一个节点的话，这个问题就能解决。具体来说，一个状态是一个 (s, x, y) 三元组，表示小明处于 (x, y) 这个位置上，无敌状态还有最后 s 秒。不考虑 #和 X 的情况，通过上下左右移动，一个状态可以到达另一个状态，比如 (3, 2, 1) 往上移动一步，就会到 (2, 1, 1) 这个状态。因为 (2, 1) 向上一格是 (1, 1)，同时无敌时间从 3 秒减少到 2 秒
如果一个位置上有无敌，比如 (2, 2) 这个格子有无敌。那么 (0, 1, 2) 与 (K+1, 2, 2) 就有边相连，因为移动到 (2, 2) 就会自动获得之后 K 秒无敌，我们认为在 (2, 2) 这个位置上时还有 K+1 秒无敌。这样 + 1 的好处是只有无敌时间 s 大于 0 才能处于陷阱上
假设 (3, 3) 上是陷阱，由于无敌才能经过陷阱，所以 (2, 2, 3), (3, 2, 3) 等分别与 (1, 3, 3), (2, 3, 3) 相连，无敌时间减 1 秒；但是 (0, 2, 3)(1, 2, 3) 与 (0, 3, 3)(1, 3, 3)(2, 3, 3) 等就没有边相连
把一个状态 (s, x, y) 看成一个节点，那么整个图中最多包含 (K+1) xNxN 个节点 (无敌时间 0~K 有 K+1 中可能，位置有 N*N 可能)； 每个节点最多有 4 个邻居（上下左右移动一步到达的状态）。起点是 (0, 0, 0) 终点有 K+1 是 (0, N-1, N-1)，(1, N-1, N-1), (2, N-1, N-1) …… (K, N-1, N-1)。起点到终点的最短路就是答案
于是在我们构建的这个图上，直接 BFS 找最短路就可以了，时空复杂度都是 $O (KNN)$ 的。代码如下：
- #include <iostream>
- #include <string>
- #include <map>
- /*
- 5 3
- ...XX
- ##%#.
- ...#.
- .###.
- .....
- */
- using namespace std;
- int n,k;//题目中的n,k
- string s[1000];
- map<int,int> dis;
- int q[12000000];
- int l,r;
- int dx[4] = {-1,1,0,0};
- int dy[4] = {0,0,-1,1};
- bool is(int x,int y)
- {
- return x >= 0 && x < n &&
- y >= 0 && y < n && s[x][y] != '#';
- }
- int main()
- {
- cin >> n >> k;
- for(int i = 0;i < n;i++)
- cin >> s[i];
- l = 0;
- r = 1;
- q[0] = 0;
- dis[0] = 0;
- while(l < r)
- {
- int st = q[l];
- int sec = st / 1000000;
- int x = st % 1000000 / 1000;
- int y = st % 1000;
- int nx,ny,nsec,nst;
- for(int d = 0;d < 4;d++)
- {
- nx = x + dx[d];
- ny = y + dy[d];
- if(is(nx,ny))
- {
- if(s[nx][ny] == '.')
- {
- if(nx == n - 1 && ny == n - 1)
- {
- cout << dis[st] + 1 << endl;
- return 0;
- }
- nsec = sec > 0 ? sec - 1 : 0;
- nst = nsec * 1000000 + nx * 1000 + ny;
- if(dis.find(nst) == dis.end())
- {
- dis[nst] = dis[st] + 1;
- q[r] = nst;
- r++;
- }
- }
- else if(s[nx][ny] == 'X')
- {
- nsec = sec > 0 ? sec - 1 : 0;
- if(nsec > 0)
- {
- nst = nsec * 1000000 + nx * 1000 + ny;
- if(dis.find(nst) == dis.end())
- {
- dis[nst] = dis[st] + 1;
- q[r] = nst;
- r++;
- }
- }
- }
- else
- {
- nsec = k + 1;
- nst = nsec * 1000000 + nx * 1000 + ny;
- if(dis.find(nst) == dis.end())
- {
- dis[nst] = dis[st] + 1;
- q[r] = nst;
- r++;
- }
- }
- }
- }
- l++;
- }
- cout << -1 << endl;
- return 0;
- }
首先我们将状态三元组 (s, x, y) 编码成一个整数 st = s 1000000 + x 1000 + y。由于 xy 的范围都小于 1000，所以上述编码的 st 与 (s, x, y) 是一一对应的。int q [] 是广搜队列，里面保存的整数就是 st。变量 l 和 r 就是之前的 head 和 tail。dis 这个 map 的作用类似之前的 steps，保存的每个状态 st 对应的最短距离，st 作为 key，距离作为 value
第 34-91 就是整个 BFS 的宽搜。第 36~39 是将队首的状态 st，解码成 (sec, x, y)，这里 sec 就是剩余无敌的秒数。然后就是循环枚举 4 个方向，算出下一个状态 (nsec, nx, ny)。第 47-62 行如果下一个状态是空地，就先看一下是不是终点，由于是广搜，第一次到达终点就是最短距离。不是终点的话就看看下一个状态在不在队列里，没在就加入队列
第 63~76 行是如果下一个状态是陷阱，那么 nsec 必须大于 0 才是合法状态，才会进一步判断下一个状态 nst 在不在队列里，没在就加入队列。第 77~87 行是在判断如果下一个状态是无敌，那么直接将无敌时间 nsec 置为 K+1。然后进一步判断下一个状态 nst 在不在队列里，没在就加入队列
上面这道题的关键就是我们能开拓思路，打破一个节点就是一个位置这样的思维惯性，想到将剩余无敌时间这个维度也” 打包 “到节点里
例 4 题目链接：hihoCoder1328展开目录
这道题和上一题有点类似，上锁的位置类似陷阱，钥匙的位置类似无敌。不过本题中钥匙拿到了就一直有效，没有持续时间；另外就是最多有 5 种不同的锁和对应钥匙。同样我们也发现只把位置信息 (x, y) 当节点的话，两个节点之间是否有边相连是不确定的。我们必须知道持有哪些钥匙，才能确定是否能走到上锁的位置上
考虑到最多有 5 把钥匙，所有持有的钥匙组合最多有 2^5 也就是 32 种情况。所以我们可以把持有钥匙的情况也加进节点里：状态 (w, x, y) 表示一个节点，其中 w 是一个 0~31 的整数，w 的二进制编码代表持有钥匙的状态。比如 w=22=$(10110)_2$ 代表持有第 2/3/5 把钥匙（最低位代表第 1 把）。(w, x, y) 就代表小 Hi 在 (x, y) 这个位置，并且持有的钥匙集合是 w
