ChaituBoi's blog

By ChaituBoi, 3 years 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
  • +8
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have better fancy your code like this

```cpp

code()

```

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey i was trying to do that. plz consider your downvote. The editor does not make it clear how to add code to it. so had to search it up

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didnt downvote you, but I found no bug in your code :(