搜索（7）

例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
 代码如下：
c++