DP O(N)

C++ 代码

class Solution {
public:
    int minSideJumps(vector<int>& obs) {
        int n = obs.size();
        int a[2][3] = {{1, 0, 1}, {-1, -1, -1}};
        // 遍历全部列
        for(int i = 1; i < n - 1; i++) {
            int mj = n;
            // 遍历全部行
            for(int j = 0; j < 3; j++) {
                // 有石头
                if(j == obs[i] - 1) a[i % 2][j] = n + 1;
                // 前面有石头，先标记一下
                else if(obs[i - 1] - 1 == j) a[i % 2][j] = -1;
                // 前面没石头，不用跳，记录最小值
                else a[i % 2][j] = a[(i-1)%2][j], mj = min(mj, a[i % 2][j]);
                // 如果这列，有2行可以通过直走到达，直走到A行再侧跳到B行，会不会相比直走到B行更优呢？
                // 不可能，因为同一列最多相差1，A的前一列比B的前一列侧跳数量小1。
                // 那么，直走到A后侧跳+1，和直走到B是一样的
            }
            // 侧跳到无法直达的地方
            for(int j = 0; j < 3; j++)
                if(a[i % 2][j] == -1) a[i % 2][j] = mj + 1;
        }
        int idx = (n-2)%2;
        return min(a[idx][0], min(a[idx][1], a[idx][2]));
    }
};

BFS最短路 O(N)

C++ 代码

class Solution {
public:
    // c = n + 1
    // id = i * c + j
    // id -> id + 1, for i in (0, 1, 2): i * c + id % c, if no stone...
    // 细节多，容易错
    int n;
    static const int maxn = (int)1.5e6 + 10;
    int dist[maxn];
    bool vis[maxn];
    int id(int i, int j) {
        return i * n + j;
    }

    int minSideJumps(vector<int>& obs) {
        this->n = obs.size();
        memset(dist, 0x3f, sizeof(dist));
        memset(vis, false, sizeof(vis));
        deque<int> q;
        q.push_back(id(1, 0));
        dist[id(1, 0)] = 0;
        while(q.size()) {
            auto t = q.front(); q.pop_front();
            if(vis[t]) continue;
            vis[t] = true;
            int x = t / n, y = t % n;
            if(y == n - 1) continue;
            if(obs[y + 1] - 1 != x) {
                int tid = t + 1;
                if(dist[t] < dist[tid])
                    dist[tid] = dist[t], q.push_front(tid);
            }
            for(int i = 0; i < 3; i++) {
                if(i == x || obs[y] - 1 == i) continue;
                int tid = id(i, y);
                if(dist[t] + 1 < dist[tid])
                    dist[tid] = dist[t] + 1, q.push_back(tid);
            }
        }
        int res = n + 1;
        for(int i = 0; i < 3; i++) res = min(res, dist[i * n + n - 1]);
        return res;
    }
};