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.

Rating changes for the last round are temporarily rolled back. They will be returned soon.
×

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 167 |

5 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

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.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 15:07:59 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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.

Nope. In the second case, BFS will go from (0, 0) to (1, 0) then straight to (1, 3). In the first case, BFS must make two steps before going to (1, 3). Hence, BFS will still take option 2 first

There is one difficulty in this problem though (if you don't use direction) — the number of transitions on each iteration of BFS can be up to O(n) if you do not code the BFS properly. So the time complexity will become O(n^3) in this case. You will need to use a simple trick to resolve this. I leave this as an exercise for you.

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.

Added my code.

Ok. There are 2 problems with your code (1 is minor enough that you can ignore anyway).

The serious problem: You are not doing the BFS properly. When you push nodes into the queue, you should check if the previously found distance is more optimal, and update the shortest distance accordingly. However, what you are doing now is to push nodes into the queue indiscriminately. This means that your queue could potentially have a lot of unnecessary nodes, which you will filter out based on distance optimality later. But this wastes computation time. Why waste time filtering unnecessary nodes?

The minor problem: LinkedList in Java is pretty slow. I think using something like ArrayList or Queue can give you better performance. But this is just some micro-optimization and you may choose to ignore it.