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. asked 24 Jul '15, 15:23

This would work for small value of n ... Let C_{i} be the i^{th} cheese.. you need to move in a manner similar to (Initial) (C_{1}) (C_{2}) (C_{3}) .... (C_{k}) (Final) Minimum moves from Initial position to final position through cheese can be easily obtained through bfs !
answered 24 Jul '15, 17:43

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 !! answered 25 Jul '15, 00:36

@meooow can u help in solving this?