MENU

搜索(7)

June 29, 2018 • Read: 280 • 算法

例3 蓝桥杯——迷宫与陷阱

image

这道题迷宫中多了一些花样。一是迷宫中有陷阱,由X表示。除非处于无敌状态,否则不能经过陷阱。二是有些位置到达后会自动获得无敌状态,持续K步

我们可以看一下样例给的两个数据:

image

这两个地图其实是一样的。区别在于左边的数据无敌状态持续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

image

这道题和上一题有点类似,上锁的位置类似陷阱,钥匙的位置类似无敌。不过本题中钥匙拿到了就一直有效,没有持续时间;另外就是最多有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
代码如下:

最后编辑于: October 19, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment