最少侧跳次数

题目

1824. 最少侧跳次数

---

给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

• 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

• 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。

这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1：

输入：obstacles = [0,1,2,3,0]
输出：2 
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

示例 2：

输入：obstacles = [0,1,1,3,3,0]
输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

示例 3：

输入：obstacles = [0,2,1,0,3,0]
输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。

提示：

• obstacles.length == n + 1
• 1 <= n <= 5 * 10^5
• 0 <= obstacles[i] <= 3
• obstacles[0] == obstacles[n] == 0

题解

方法一：

思路

动态规划做法
可以简单设f[i][j]为第i行j列的最少跳跃次数。
为方便实现，用第0列作为哨兵，所以答案是min(f[i][n+1])。

初始f[1][0] = 1。

状态转移

可以由同一列的非障碍位置侧跳过来f[k][j]+1->f[i][j], k!=i。

也可以由前一列同一行非障碍位置直跳过来f[i][j-1]->f[i][j]。

由于同列侧跳有后效性，可以有前一列不同行侧跳过来f[k][j-1]+1->f[i][j], k!=i。

代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int f[3][500005]; //f[i][j] 到达i行j列需要侧跳的最小次数。
    // init f[i][j] = inf, f[1][0] = 0
    // ans min(f[i][n+1])
    int minSideJumps(vector<int>& obstacles) {
        memset(f, 0x3f, sizeof(f));
        f[1][0] = 0;
        int sz = obstacles.size();
        for (int i=1; i<=sz; i++) {
            if (obstacles[i-1]) f[obstacles[i-1]-1][i-1] = INF;
            f[0][i] = min({f[0][i-1], f[1][i-1]+1, f[2][i-1]+1});
            f[1][i] = min({f[0][i-1]+1, f[1][i-1], f[2][i-1]+1});
            f[2][i] = min({f[0][i-1]+1, f[1][i-1]+1, f[2][i-1]});
            if (obstacles[i-1]) f[obstacles[i-1]-1][i] = INF;
            // cout << f[0][i] << " " << f[1][i] << " " << f[2][i] << endl;
        }
        return min({f[0][sz], f[1][sz], f[2][sz]});
    }
};

方法二：

思路

01BFS

建图

对于非障碍位置作为图中点。

当位置(i, j)移动到(i, j+1)时建立权值为0的边

当位置(i, j)移动到(k, j)时建立权值为1的边, i!=k。

这是图中边权不是0就是1，可以用dijkstra算法求出每个点到起点的最短路即可。

但是实际上在如果用01BFS可以更快。

dis[i]作为起点到i的最短距离

用双端队列进行BFS，保证队列中每个节点到起点的距离从小到大排序。

对于边权为 0 的边 x→y，如果 dis[x]<dis[y]，更新 dis[y]=dis[x]，把 y 加到队首。由于队首x到起点的距离最小，而y到起点的距离已经于x相等，所以y放队首理应最小。

对于边权为 1 的边 x→y，如果 dis[x]+1<dis[y]，更新 dis[y]=dis[x]+1，把 y 加到队尾。

一个节点第一次出队这个节点到顶点的最短距离就确定了。再次出队不会比之前更优。

代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int minSideJumps(vector<int>& obstacles) {
        int sz = obstacles.size();
        vector<vector<int>> dis(3, vector<int>(sz, INF));
        dis[1][0] = 0;
        deque<pair<int,int>> q;
        q.emplace_front(1, 0);
        while (q.size()) {
            auto [r,c] = q.front(); q.pop_front();
            if (c+1<sz && obstacles[c+1]-1 != r && dis[r][c+1]>dis[r][c]) {
                dis[r][c+1] = dis[r][c];
                q.emplace_front(r,c+1);
            }
            for (int i=0; i<3; i++) {
                if (i == r || obstacles[c]-1 == i || dis[i][c]<=1+dis[r][c]) continue;
                dis[i][c] = 1 + dis[r][c];
                q.emplace_back(i, c);
            }
        }
        return min({dis[0][sz-1], dis[1][sz-1], dis[2][sz-1]});
    }
};