You are not logged in. Please login at to post your questions!


How to solve this maze problem.

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

anu1234's gravatar image

accept rate: 0%

@meooow can u help in solving this?

(26 Oct '17, 23:42) beginner_11114★

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

adkroxx's gravatar image

accept rate: 7%

the problem appears to be a travelling salesman 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

coolsduy's gravatar image

accept rate: 25%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 24 Jul '15, 15:23

question was seen: 8,710 times

last updated: 26 Nov '17, 18:43