Help needed for Q: min jumps to reach home

Revision en1, by ChaituBoi, 2020-11-19 13:11:15

Question statement: A certain bug's home is on the x-axis at position x. Help them get there from position 0. The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right). It can jump exactly b positions backward (to the left). It cannot jump backward twice in a row. It cannot jump to any forbidden positions. The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

1 <= forbidden.length <= 1000

1 <= a, b, forbidden[i] <= 2000

0 <= x <= 2000

Solution: Tried making graph of size 4001 and then bfs to find the answer. I am getting wrong answer on test case: [14,4,18,1,15] //forbidden array

40 //a

12 //b

1300 //x

MY CODE:

class Solution {

unordered_map<int,bool>mp;

int ul=4001; /*no real proof on upperlimit( might be wrong. please provide insight), but going too many jumps forward and then backwards to reach home can be equivalent to jumping forward and backward alternately! SO do not need to have more than these many nodes.*/

public: void populate(vectoradj[],vector&vis,int i,int &a,int &b)//,int &x,bool back) {

for(i=0;i<ul;i++)
    {
        if(i+a<ul && mp.find(i+a)==mp.end())
            adj[i].push_back(i+a);
        if(i-b>=0 && mp.find(i-b)==mp.end())
            adj[i].push_back(i-b);
    }
}
int bfs(vector<int>adj[],vector<bool>&vis,int &a,int &b,int &x)
{
    queue<pair<int,bool>>q;
    int step=0,num_now=0,num_next=1;
    q.push({0,false});
    while(!q.empty())
    {
        step++;
        num_now=num_next;
        num_next=0;

        while(num_now--)
        {
            int temp=q.front().first; //temp=current node
            bool back=q.front().second;//back => did i reach temp using a backward jump?
            q.pop();
            // vis[temp]=true;
            if(temp==x)
                return step-1;
            for(int i=0;i<adj[temp].size();i++)
            {
                int neigh=adj[temp][i];
                if(!vis[neigh] && (neigh==temp+a or (neigh==temp-b && !back)))//if neighbour awaits forward jump,go for it , if backward jump? check if back false or not
                {  
                    vis[neigh]=true;
                    q.push({neigh,neigh==temp-b});
                    num_next++;
                }
            }
        }

    }
    return -1;
}
int minimumJumps(vector<int>& forbidden, int a, int b, int x) {//The main function

    vector<int>adj[ul];
    vector<bool>vis(ul,false); 
    int n=forbidden.size();
    for(int i=0;i<n;i++)//mapping forbidden nodes for quick access
        mp[forbidden[i]]=true;

    populate(adj,vis,0,a,b);        

    n=bfs(adj,vis,a,b,x);
    mp.clear();
    return n;
}

};

Tags #wronganswer, #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ChaituBoi 2020-11-19 13:11:15 3494 Initial revision (published)