rr459595's blog

Interviewbit Question:- Rook Movement
By rr459595, history, 7 years ago, In English

Link to the question:- https://www.interviewbit.com/problems/rook-movement/

I tried BFS where in each state I store min steps,direction (up,down,left or right). I am getting TLE for large inputs.

Can someone help me ?

Thanks.

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

Comments Comments (4)
| Write comment?
»
7 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Why do you need to store the direction? BFS will never revisit the same cell due to the shortest number of steps property. And I also don't understand how you can get TLE because the input is small. Try posting your code here.

→ Reply
  • »
    »
    7 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I thought that direction is required.

    Consider the eg:-

    000111

    000000

    where '1' denotes obstacles.

    We can visit (1,2) in 2 steps in 2 ways from (0,0):-

    1) (0,2) and (1,2)

    2) (1,0) and (1,2).

    Now if destination is (1,3), we would prefer 2nd) option over first as using first option would give 3 steps as answer but optimal answer to reach (1,3) should be 2.

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

Anyway, your method works as well. Just that I don't understand how you got TLE. Posting some code would certainly help people to determine the cause of the problem.

→ Reply