Page 2 of 2

Re: 10496 - Collecting Beepers

Posted: Sun Dec 21, 2008 8:28 pm
by mf
Greedy shouldn't work here.

BFS can work, with a special graph, of course - each state should be a triple (x, y, m), where m is a bitmask, representing the subset of collected beepers.

Re: 10496 - Collecting Beepers

Posted: Mon Dec 22, 2008 12:37 am
by Articuno
Thank you mf. I will try to sove it using BFS. Thanks for ur help. :)

Re: 10496 - Collecting Beepers

Posted: Wed Oct 27, 2010 4:51 pm
by Shafaet_du
I solved it using recursive backtracking.

Re: 10496 - Collecting Beepers

Posted: Fri Apr 04, 2014 6:32 am
by dhruba07
This problem can be solved by recursive backtracking.

The only thing to look at is :http://en.wiktionary.org/wiki/Manhattan_distance

Because this grid has no obstacles in path, so the distance can be directly calculated by Manhattan Distance.

So choose one beeper,backtrack and then choose another :D


Thanks Brianfry for his concern :)

Re: 10496 - Collecting Beepers

Posted: Fri Apr 04, 2014 9:00 pm
by brianfry713
Post your full code.