ChaituBoi's blog

By ChaituBoi, history, 7 months ago, In English

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;
}

};

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

here is good explanation about this question.