BFS: Jump Game IV

1345. Jump Game IV

Jimmy (xiaoke) Shen

·

Follow

2 min read

·

Dec 28, 2020

--

Listen

Share

Using pair to record the index and depth

const int N = 5e4 + 10;
int f[N];
class Solution {
public:
    int minJumps(vector<int>& arr) {
        memset(f, 0, sizeof(f));
        const int n = arr.size();
        if (n == 1) return 0;
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < n; ++i) {
            //if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;
            m[arr[i]].push_back(i);
        }
        deque<pair<int, int>> dq;
        dq.emplace_back(n-1, 0);
        int ret = 0;
        while (true) {
            auto [k, depth] = dq.front();dq.pop_front();
            if (k == 0) {
                return depth;
            }
            for (auto &x: m[arr[k]]) {
                if (x != k && !f[x]) {
                    f[x] = 1;
                    if (x == 0) return depth + 1;
                    dq.emplace_back(x, depth + 1);
                }
            }
            for (auto di : {-1, 1}) {
                if (k + di < n && k + di >= 0 && !f[k + di]) {
                    f[k + di] = 1;
                    if (k + di == 0) return depth + 1;
                    dq.emplace_back( k + di, depth + 1);
                }
            }
        }
        return ret;
        
    }
};

A better way

const int N = 5e4 + 10;
bool f[N];
class Solution {
public:
    int minJumps(vector<int>& arr) {
        memset(f, 0, sizeof(f));
        const int n = arr.size();
        if (n==1) return 0;
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < n; ++i) {
            if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;
            m[arr[i]].push_back(i);
        }
        deque<int> dq;
        dq.emplace_back(n-1);
        int ret = 0;
        int depth = 1;
        f[n-1] = true;
        while (true) {
            int sz = dq.size();
            for (int i = 0; i < sz; ++i) {
                int k = dq.front(); dq.pop_front();
                if (k == 0) return depth;
                for (auto &x: m[arr[k]]) {
                    if (x != k &&  !f[x]) {
                        f[x] = true;
                        if (x == 0) return depth;
                        dq.push_back(x);
                    }
                }
                for (auto di : {-1, 1}) {
                    if (k + di < n && k + di >= 0 && !f[k + di]) {
                         f[k + di] = true;
                        if (k + di == 0) return depth;
                        dq.push_back(k + di);
                    }
                } 
            }
            depth++;
        }
        
        return ret;  
    }
};