这是 2020 年 7 月 29 日的每日一题。感受到了真正的恐怖,记录一下吧。

题目

我们得到了一副藏宝图,藏宝图显示,在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵,用一个字符串数组表示。它标识了唯一的入口(用 'S' 表示),和唯一的宝藏地点(用 'T' 表示)。但是,宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点(用 'M' 表示),只有所有机关均被触发,才可以拿到宝藏。

要保持机关的触发,需要把一个重石放在上面。迷宫中有若干个石堆(用 'O' 表示),每个石堆都有 无限 个足够触发机关的重石。但是由于石头太重,我们一次只能搬 一个 石头到指定地点。

迷宫中同样有一些墙壁(用 '#' 表示),我们不能走入墙壁。剩余的都是可随意通行的点(用 '.' 表示)。石堆、机关、起点和终点(无论是否能拿到宝藏)也是可以通行的。

我们每步可以选择向上/向下/向左/向右移动一格,并且不能移出迷宫。搬起石头和放下石头不算步数。那么,从起点开始,我们最少需要多少步才能最后拿到宝藏呢?如果无法拿到宝藏,返回 -1 。

限制

  • 1 <= maze.lenght <= 100
  • 1 <= maze[i].length <= 100
  • maze[i].length == maze[j].length
  • S 和 T 有且只有一个
  • O <= M 的数量 <= 16
  • 0 <= O 的数量 <= 40, 题目保证当迷宫中存在 M 时,一定存在至少一个 O。

示例 1

输入: ["S#O", "M..", "M.T"]

输出:16

解释:最优路线为: S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2,去T点拿宝藏。 总步数为16。

6bfff669ad65d494cdc237bcedfec10a2b1ac2f2593c2bf97e9aecb41dc8a08b-图片.gif

示例 2

输入: ["S#O", "M.#", "M.T"]
输出:-1

解释:我们无法搬到石头触发机关

示例 3

输入: ["S#O", "M.T", "M.."]
输出:17

解释:注意终点也是可以通行的。

预处理

首先我们先把特殊点取出来,建立一个 index 到 特殊点坐标的关系:

vector<pair<int, int>> o;
vector<pair<int, int>> m;
pair<int,int> s;
pair<int, int> t;

for(int i = 0 ; i < maze.size() ; i ++){
    for(int j = 0 ; j < maze[i].size() ; j ++){
        switch (maze[i][j]) {
            case 'S':
                s = {i, j};
                break;
            case 'T':
                t = {i, j};
                break;
            case 'M':
                m.emplace_back(i,j);
                break;
            case 'O':
                o.emplace_back(i, j);
                break;
        }
    }
}

因为迷宫是静态的,所以任意两个点之间的最短距离是确定的。这里我们先写一个深搜方法来获取两点间的最短距离:(绕开墙壁)

这里使用队列来进行深搜。移动的向量坐标也用一个集合储存,这个技巧在图中经常用到(走迷宫也可以看成图)

如果两点不可达,则设置为 -1

vector<pair<int,int>> next_v = {{0,1},{0,-1},{1,0},{-1,0}};

int bfs(pair<int,int> A, pair<int,int> B, vector<string>& maze){
    queue<pair<pair<int,int>,int>> q;
    vector<vector<int>> visit (maze.size(), vector<int>(maze[0].size(),0));

    q.push({A,0});
    visit[A.first][A.second] = 1;
    while(!q.empty()){
        auto p = q.front().first;
        auto z = q.front().second;
        q.pop();

        if(p.first == B.first && p.second == B.second){

            return z;
        }

        for(auto next : next_v){

            int newI = p.first + next.first;
            int newJ = p.second + next.second;

            if(newI >= 0 && newI < maze.size()
            && newJ >= 0 && newJ < maze[0].size()){
                if(maze[newI][newJ] != '#'){
                    if(visit[newI][newJ] == 0){
                        q.push({{newI,newJ},z+1});
                        visit[newI][newJ] = 1;
                    }
                }
            }

        }
    }
    return -1;
}

然后我们遍历所有的特殊点,先计算出所有机关点到石头点的最短距离,在通过这个距离遍历机关到石头再到机关所有情况的最短距离:

同样如果不可达就设为 -1

vector<vector<int>> o2m(o.size(), vector<int>(m.size(),-1));
vector<vector<int>> m2m(m.size(), vector<int>(m.size(),-1));


for(int oI = 0; oI < o.size() ; oI ++){
    for(int mI = 0; mI < m.size() ; mI ++){
        o2m[oI][mI] = bfs(o[oI],m[mI],maze);
    }
}


for(int mI = 0; mI < m.size() ; mI ++){
    for(int mJ = mI; mJ < m.size() ; mJ ++){
        int value = INT_MAX;
        for(int oI = 0; oI < o.size() ; oI ++){
            if (o2m[oI][mI] == -1 || o2m[oI][mJ] == -1){
                continue;
            }
            value = min(value, o2m[oI][mI]+o2m[oI][mJ]);
        }
        if (value != INT_MAX){
            m2m[mI][mJ] = value;
            m2m[mJ][mI] = value;
        }else{
            m2m[mI][mJ] = -1;
            m2m[mJ][mI] = -1;
        }

    }
}

然后保存一下起点-石堆-机关和机关到终点的所有情况:

vector<int> s2m(o.size());
vector<int> m2t(m.size());

for(int mI = 0; mI < m.size() ; mI ++){
    int value = INT_MAX;
    for(int oI = 0; oI < o.size() ; oI ++){
        int s2o = bfs(s,o[oI],maze);
        if(s2o != -1 && o2m[oI][mI] != -1){
            value = min(value,s2o+o2m[oI][mI]);
        }
        if (value != INT_MAX){
            s2m[mI] = value;
        }else{
            s2m[mI] = -1;
        }
    }
}
for(int mI = 0; mI < m.size() ; mI ++){
    m2t[mI] = bfs(m[mI],t,maze);
}

至此,所有准备活动我们都完成了。来梳理一下,现在我们知道了机关-石堆-机关的任意情况下的最短路径,我们可以看成是在机关-机关的最短路径。还有起点-石堆-机关,机关到终点。

此时我们可以抛开迷宫了,单独把起点终点和机关抽象出来,如下图:

S054UXD(JQFBT{~91_9S425.png

注意这里的距离是包括去石堆拿石头的距离,所以并不是迷宫里的距离,因为距离是不确定的,所以他们的排列也是不确定的,这里图只是画了其中的某一种情况。

于是问题就转变为了:

已知任意两点间的距离,求经过所有点的最短路径。

这个问题可以用动态规划解决。

动态规划

这种问题是动态规划的一种典型问题。可以用到状态压缩。

首先我们规定一个 k 位的二进制数 mask。这里的 k 是机关的数量。其中第 i 位数表示第 k-i 个机关的的状态(也就是有没有经过的状态)。

这里以 示例1 为例,有两个机关,所以这个 mask 是两位二进制数。具体取值:

00 两个机关都没启动
01 第一个机关启动了,第二个机关还没启动
10 第一个机关没启动,第二个机关启动了
11 两个机关的启动了

注意:这里第一个机关对应着二进制最右边的一位数,这是为了方便之后计算。

然后先补充一些位运算:

// 获取只有第 i 位数(从右数从 0 开始)为 1 其他都是 0 的二进制数
1<<i

// 判断二进制数 第 i 位是不是 1
if(mask|(1<<i) == mask) 

// 改变二进制数第 i 位 ( 0 变 1 ,1 变 0)
mask xor (1<<i)

状态方程

这里定义状态方程 $dp(mask, j)$ 为从起点出发,要达到 mask 这种状态,且最后一个激活的机关为 j 所需要的最小步数。可能有点绕,不过还是可以理解的。

注意,这里 j 为最后一个激活的机关,也就是说 mask 这种状态下,第 j 个机关一定是已经激活的,否则就没有意义。

然后开始思考状态转移:

这里我们知道 j 为最后一个激活的机关,那么我们可以在 mask 里除了 j 以外的一个已经激活的机关上一个 i

此时:

$$ dp(mask, j) = dp(lastMask,i)+m2m[i][j] $$

$$ lastMask = mask \oplus (1 << i) $$

即假设第 i 个机关刚开启的情况再加上从 ij 的距离。

我们可以当前 mask 下的所有 i 然后取最小值。所以总的状态转移方程为:

$$ dp(mask, j) = \underset{mask|(1<<i) == mask}{\min}(dp(lastMask,i)+m2m[i][j]) $$

$$ lastMask = mask \oplus (1 << i) $$

边界条件也很好处理,因为我们需要遍历上一个打开的机关的,所以没有上一个打开的机关也就是边界条件,即 mask 只有一个 1,此时刚好就是起点到那个机关的距离

$$ dp(mask, j) = s2m[j],if \ mask=1<<j $$

上代码咯:注意,这里代码和普通的状态转移有点区别,这里 for循环里是先遍历了 i ,然后在遍历 j ,然后比较状态函数的值。

int result = INT_MAX;
int maxx = 1 << m.size();
vector<vector<int>> dp(maxx,vector<int>(m.size(), -1));
// 边界条件
for(int mJ = 0; mJ < m.size() ; mJ ++){
    dp[(1 << mJ)][mJ] = s2m[mJ];
}

// 因为你打开任意一个机关都是把一个 0 变成 1,都是增大,所以状态值直接递增即可
for(int mask = 1; mask < maxx ; mask ++){

    // 遍历 I
    for(int mI = 0; mI < m.size() ; mI ++){
        // 无效状态,当前第 i 个机关没打开
        if (mask != (mask|(1<<mI))){
            continue;
        }
        if(dp[mask][mI] == -1){
            continue;
        }
        for(int mJ = 0; mJ < m.size() ; mJ ++){

            // 第 j 个已经打开了,不需要转移了
            if (mask == (mask|(1<<mJ))){
                continue;
            }
            if(mI == mJ){
                continue;
            }

            // 不可达
            if(m2m[mI][mJ] == -1){
                continue;
            }

            // 将 j 打开后的状态
            int nextMask = mask |(1<<mJ);

            //状态转移
            if (dp[nextMask][mJ] == -1 || dp[nextMask][mJ] > dp[mask][mI] + m2m[mI][mJ]) {
                if(dp[mask][mI] != -1)
                    dp[nextMask][mJ] = dp[mask][mI] + m2m[mI][mJ];
            }

        }
    }
}

结果获取

动态规划完,我们得到了一个 dp 函数。此时为了得到最终结果,我们需要遍历 dp 函数中所有机关都激活的情况。根据最后一个激活的机关再加上机关到终点的距离,并获取最小值。上代码:

result = INT_MAX;

for(int mI = 0 ; mI < m.size() ; mI ++){
    if (dp[maxx-1][mI] != -1 && m2t[mI] != -1){
        result = min(dp[maxx-1][mI] + m2t[mI],result);
    }

}


if (result == INT_MAX){
    result = -1;
}

return result;

后记

以上代码已经通过的测试,只不过超时了。不过我看了别人的提交,大都是改了变量名,思路也差不多。不知道为啥会超时。所以我是直接复制题解交的。

这道题本质上是已知两两距离找最短路径的问题,使用动态规划 + 状态压缩解决。

主要是这道题把本质藏了起来,你需要思考到所有点的最短距离是不变的,然后通过深搜获取所有路径,最后转化为动态规划求解。不得不说秒啊。

总代码

class Solution {

    vector<pair<int,int>> next_v = {{0,1},{0,-1},{1,0},{-1,0}};

public:
    int minimalSteps(vector<string>& maze) {

        pair<int,int> s;
        vector<pair<int, int>> o;
        vector<pair<int, int>> m;
        pair<int, int> t;



        for(int i = 0 ; i < maze.size() ; i ++){
            for(int j = 0 ; j < maze[i].size() ; j ++){
                switch (maze[i][j]) {
                    case 'S':
                        s = {i, j};
                        break;
                    case 'T':
                        t = {i, j};
                        break;
                    case 'M':
                        m.emplace_back(i,j);
                        break;
                    case 'O':
                        o.emplace_back(i, j);
                        break;
                }
            }
        }

        if(m.size() == 0){
            return dfs(s,t,maze);
        }

        vector<vector<int>> o2m(o.size(), vector<int>(m.size(),-1));
        vector<vector<int>> m2m(m.size(), vector<int>(m.size(),-1));

        vector<int> s2o(o.size(),-1);
        vector<int> s2m(m.size(),-1);
        vector<int> m2t(m.size(),-1);

        for(int oI = 0; oI < o.size() ; oI ++){
            for(int mI = 0; mI < m.size() ; mI ++){
                o2m[oI][mI] = dfs(o[oI],m[mI],maze);
            }
        }


        for(int mI = 0; mI < m.size() ; mI ++){
            for(int mJ = mI; mJ < m.size() ; mJ ++){
                int value = INT_MAX;
                for(int oI = 0; oI < o.size() ; oI ++){
                    if (o2m[oI][mI] == -1 || o2m[oI][mJ] == -1){
                        continue;
                    }
                    value = min(value, o2m[oI][mI]+o2m[oI][mJ]);
                }
                if (value != INT_MAX){
                    m2m[mI][mJ] = value;
                    m2m[mJ][mI] = value;
                }else{
                    m2m[mI][mJ] = -1;
                    m2m[mJ][mI] = -1;
                }

            }
        }



        for(int oI = 0; oI < o.size() ; oI ++){
            s2o[oI] = dfs(s,o[oI],maze);
        }
        for(int mI = 0; mI < m.size() ; mI ++){
            m2t[mI] = dfs(m[mI],t, maze);
        }
        for(int mI = 0; mI < m.size() ; mI ++){
            int value = INT_MAX;
            for(int oI = 0; oI < o.size() ; oI ++){
                if(s2o[oI] != -1 && o2m[oI][mI] != -1){
                    value = min(s2o[oI]+o2m[oI][mI], value);
                }
            }
            if(value == INT_MAX){
                s2m[mI] = -1;
            }else{
                s2m[mI] = value;
            }
            
        }

        int result = INT_MAX;
        int maxx = pow(2,m.size());
        vector<vector<int>> dp(maxx,vector<int>(m.size(), -1));


        for(int mask = 0; mask < maxx ; mask ++){

            if(mask == 0){

                for(int mJ = 0; mJ < m.size() ; mJ ++){
                    dp[(1 << mJ)][mJ] = s2m[mJ];
                }

            }else{
                for(int mI = 0; mI < m.size() ; mI ++){
                    if (mask != (mask|(1<<mI))){
                        continue;
                    }
                    if(dp[mask][mI] == -1){
                        continue;
                    }
                    for(int mJ = 0; mJ < m.size() ; mJ ++){
                        if (mask == (mask|(1<<mJ))){
                            continue;
                        }
                        if(mI == mJ){
                            continue;
                        }
                        if(m2m[mI][mJ] == -1){
                            continue;
                        }
                        int nextMask = mask |(1<<mJ);

                        if (dp[nextMask][mJ] == -1 || dp[nextMask][mJ] > dp[mask][mI] + m2m[mI][mJ]) {
                            if(dp[mask][mI] != -1)
                                dp[nextMask][mJ] = dp[mask][mI] + m2m[mI][mJ];
                        }
                    }
                }
            }
        }

        result = INT_MAX;

        for(int mI = 0 ; mI < m.size() ; mI ++){
            if (dp[maxx-1][mI] != -1 && m2t[mI] != -1){
                result = min(dp[maxx-1][mI] + m2t[mI],result);
            }

        }


        if (result == INT_MAX){
            result = -1;
        }

        return result;
    }


    int dfs(pair<int,int> A, pair<int,int> B, vector<string>& maze){
        queue<pair<pair<int,int>,int>> q;
        vector<vector<int>> visit (maze.size(), vector<int>(maze[0].size(),0));

        q.push({A,0});
        visit[A.first][A.second] = 1;
        while(!q.empty()){
            auto p = q.front().first;
            auto z = q.front().second;
            q.pop();

            if(p.first == B.first && p.second == B.second){
                return z;
            }

            for(auto next : next_v){

                int newI = p.first + next.first;
                int newJ = p.second + next.second;

                if(newI >= 0 && newI < maze.size()
                    && newJ >= 0 && newJ < maze[0].size()){
                    if(maze[newI][newJ] != '#'){
                        if(visit[newI][newJ] == 0){
                            q.push({{newI,newJ},z+1});
                            visit[newI][newJ] = 1;
                        }
                    }
                }

            }


        }
        return -1;

    }

};
文章目录