Блог пользователя rr459595

Interviewbit Question:- Rook Movement
Автор rr459595, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить