×

# How to solve this maze problem.

 1 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 1★anu1234 114●3●10●18 accept rate: 0% @meooow can u help in solving this? (26 Oct '17, 23:42)

 1 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 ! answered 24 Jul '15, 17:43 6★adkroxx 306●7●19 accept rate: 7%
 0 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 2★coolsduy 165●9 accept rate: 25%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,738
×1,664
×148
×92

question asked: 24 Jul '15, 15:23

question was seen: 8,710 times

last updated: 26 Nov '17, 18:43