iamdumb's blog

This question using BFS ?

By iamdumb, 10 years ago, In English

Can anybody please tell me how do i approach this question Two-Buttons using BFS. I know how to do this other way but not using BFS(new to graph algorithms :) ).And why did we use BFS not DFS.In what scenario we use DFS and in What BFS.Thanks

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

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In every step you can choose multiple the current number by 2 or subtract 1. And for every new number you can do the same recursively.

Example (First input):

Input:

4 6

    4
 /    \
3      8
| \    |  \
2  6   7   16

Output:

2

Using BFS you can found the shortest path from 4 to 6 in this example is 2.

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

    Thanks a lot..But why did you use BFS ?You could have used DFS instead

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

      DFS doesn't work, because the first goal you reach in your DFS tree is not necessarily optimal.

      Suppose say, you find the goal node in your DFS tree at depth k, but it is certainly possible that there exists another goal node located at depth < k. You just haven't explored that goal yet.

      → Reply