ramJha's blog

Please Help..

By ramJha, history, 3 years ago, In English

You are given 'N' stairs and f,p,u,d where f=final postion to reach; p=initial position u=steps jump in forward direction; d=steps jump in backward direction; and cant go ouside the N stairs find the min steps required to reach from 'p' to 'f';

Ex: n=8 f=1 p=6 u=2 d=1

ans=4

explanation:

1->3->5->4->6

  • Vote: I like it
  • -7
  • Vote: I do not like it

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

Problem Link

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is just a bfs. The initial state is at p. For any state you keep the number of button pushes to get there as well as if you ever got there. Then from a state s you can go to s+u or to s-d(you should also check that they are in valid positions >0 && <=n).

For the given example you would have:

min={0, -1, -1, -1, -1, -1, -1, -1, -1, -1}, queue={1}

Update min[1+2]

min={0, -1, 1, -1, -1, -1, -1, -1, -1, -1}, queue={3}

Update min[3+2] and min[3-1]

min={0, 2, 1, -1, 2, -1, -1, -1, -1, -1}, queue={5, 2}

Update min[5+2] and min[5-1]

min={0, 2, 1, 3, 2, -1, 3, -1, -1, -1}, queue={2, 7, 4}

Don't update min[2+2] and min[2-1]

min={0, 2, 1, 3, 2, -1, 3, -1, -1, -1}, queue={7, 4}

Update min[7+2] and min[7-1]

min={0, 2, 1, 3, 2, 4, 3, -1, 4, -1}, queue={4, 9, 6}

Don't update min[4+2] and min[4-1]

min={0, 2, 1, 3, 2, 4, 3, -1, 4, -1}, queue={9, 6}

Update min[9-1]

min={0, 2, 1, 3, 2, 4, 3, 5, 4, -1}, queue={6, 8}

Don't update min[6+2] and min[6-1]

min={0, 2, 1, 3, 2, 4, 3, 5, 4, -1}, queue={8}

Update min[8+2]

min={0, 2, 1, 3, 2, 4, 3, 5, 4, 6}, queue={10}

The program ends for you have reached the final state and the answer is min[f]

→ Reply