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.

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

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

1 | Errichto | 198 |

2 | antontrygubO_o | 191 |

3 | pikmike | 185 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Um_nik | 177 |

7 | Radewoosh | 174 |

8 | SecondThread | 169 |

9 | Monogon | 163 |

10 | McDic | 162 |

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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2020 15:26:22 (h3).

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.

Can you please post your working code here? Thank you

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.

Can you please have a look at my code and let me know my mistake please?

https://ide.geeksforgeeks.org/eXFGq0rJQC

Thank you!

You can easily write brute force algo and check that against your own code's result. Until you have done that, I won't debug for you.

This was the only solution that I was able to think of...What is the brute force solution that you are talking about? Thank you

Explore all possible paths with a recursive dfs.