【Leetcode】1824. Minimum Sideway Jumps

题目地址：

https://leetcode.com/problems/minimum-sideway-jumps/description/

给定一条宽为$3$的路，可以视为三条平行线，给定一个长$n+1$的数组$A$，$A[i]=0$表示位置$i$无障碍物，$A[i]=k>0$表示位置$i$的第$k$条线有障碍物。一只青蛙在位置$0$的第二条平行线出发，可以以代价$0$向右跳一步，也可以以代价$1$变线，只是不能跳到障碍物上。题目保证$A[0]=A[n]=0$，问要跳到位置$n$的最小代价。

可以将所有位置看成是图上的点，代价视为边权，则代价只有$0,1$两种，从而是一个$01$图上的最短路问题，可以用双端队列BFS来做，参考https://blog.csdn.net/qq_46105170/article/details/114667171。代码如下：

class Solution {
 public:
  using PII = pair<int, int>;
  int minSideJumps(vector<int>& obstacles) {
    int n = obstacles.size() - 1;
    deque<PII> dq;
    dq.push_back({0, 2});
    bool vis[n + 1][3];
    memset(vis, 0, sizeof vis);
    int dist[n + 1][3];
    memset(dist, 0x3f, sizeof dist);
    dist[0][1] = 0;
    while (dq.size()) {
      auto t = dq.front();
      dq.pop_front();
      int x = t.first, y = t.second;
      if (x == n) return dist[x][y - 1];
      if (vis[x][y - 1]) continue;
      vis[x][y - 1] = true;
      if (obstacles[x + 1] != y && !vis[x + 1][y - 1] &&
          dist[x + 1][y - 1] > dist[x][y - 1]) {
        dist[x + 1][y - 1] = dist[x][y - 1];
        dq.push_back({x + 1, y});
      }
      for (int k = 1; k <= 3; k++)
        if (k != y && k != obstacles[x] && !vis[x][k - 1] &&
            dist[x][k - 1] > dist[x][y - 1] + 1) {
          dist[x][k - 1] = dist[x][y - 1] + 1;
          dq.push_back({x, k});
        }
    }

    return -1;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

时空复杂度$O(n)$。