There is a maze of size n*n. Tom is sitting at (0,0). Jerry is sitting in another cell (the position of Jerry is input). Then there are k pieces of cheese placed in k different cells (k <= 10). Some cells are blocked while some are not. Tom can move to 4 cells at any point of time (left, right, up, down one position). Tom has to collect all the pieces of cheese and then reach to Jerry’s cell. You need to print the minimum no. of steps required to do so.
I can solve this problem recursively but that is too complex , how can we do better?I can’t think any DP solution as we can go in all 4 directions.
1 Like
This would work for small value of n …
Let Ci be the ith cheese… you need to move in a manner similar to
(Initial) (C1) (C2) (C3) … (Ck) (Final)
Minimum moves from Initial position to final position through cheese can be easily obtained through bfs !
And since there are only k! permutation possible and k<=10 , it is possible to check all arrangements naively !
1 Like
the problem appears to be a travelling salesman problem…as k<=10…there are at max 10! possibilities…
first using floydwarshall compute all pair shortest paths…then just check all possible arrangements and compute the minimum steps !!
@meooow can u help in solving this?