You are not logged in. Please login at www.codechef.com 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

1★anu1234
11431018
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 !

link

answered 24 Jul '15, 17:43

adkroxx's gravatar image

6★adkroxx
306719
accept rate: 7%

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 !!

link

answered 25 Jul '15, 00:36

coolsduy's gravatar image

2★coolsduy
1659
accept rate: 25%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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